Problem Link - Greg and Grid in Number theory
Problem Statement:
Recently, Greg got a grid with n rows and m columns. Rows are indexed from 1 to n and columns are indexed from 1 to m. The cell (i,j) is the cell of intersection of row i and column j. Each cell has a number written on it. The number written on cell (i,j) is equal to (i+j).
Now, Greg wants to select some cells from the grid, such that for every pair of selected cells, the numbers on the cells are co-prime. Determine the maximum number of cells that Greg can select.
Approach:
- The function SieveOfEratosthenes(int num) computes the number of prime numbers less than or equal to num. This is useful because the maximum set of co-prime numbers that can be formed will be prime numbers.
- We will call the function for (n+m) as the maximum number that can be formed is n+m and count for total number of prime numbers.
- See for reference:- Sieve of Eratosthenes in Number theory
Complexity:
- Time Complexity:
O((n+m) log log (n+m))for sieve of eratothenes. - Space Complexity:
O(n)to store prime array