Last Updated: 14 Dec, 2022
Co-Prime
Hard
Asked in company
You have an integer ‘N’. Now let’s define a function ‘f(x)’ equal to the number of integers not more than ‘x+1’ and greater than equal to ‘1’ and are coprime to integer ‘x’.
Let’s say there is a number ‘X’ divided by ‘K’ different prime numbers, and let array ‘P’ of length ‘K’ be the array of prime numbers dividing the number ‘X’.
So ‘g(X)’ is equal to the sum of ∑f(X/Pi) ‘i’ in the range ‘[0, K-1]’ both inclusive.
Construct an array ‘Y’ of length ‘N’ where ‘Y[i]’= ‘g(i+1)’ for ‘i’ in the range ‘[0, N-1]’.
Determine the array ‘Y’.
Example:
'N' = 3
First calculate ‘f(1)’, ‘f(2)’ and ‘f(3)’.
‘f(1)’ = ‘2’ as ‘1’ and ‘2’ are co-prime to ‘1’.
‘f(2)’ = ‘2’ as ‘1’ and ‘3’ are co-prime to ‘2’.
‘f(3)’ = ‘3’ as ‘1’, ‘2’ and ‘4’ are co-prime to ‘3’.
Now calculate ‘g(1)’ , ‘g(2)’, ‘g(3)’.
‘g(1)’ as no prime number divides 1, so ‘g(1) = 0’.
‘g(2)’ = ‘f(2/2)’ = ‘f(1) = 2’ as ‘2’ is the only prime number that divides ‘2’.
‘g(3) = ‘f(3/3)’ = ‘f(1) = 2’ as ‘3’ is the only prime number that divides ‘3’.
Input Format:
The first line contains an integer 'T', which denotes the number of test cases to be run. Then the test cases follow.
The first line of each test case contains one integer, 'N'.
Output format:
For each test case, output the array ‘Y’.
Note :
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N <= 10^5
Time Limit: 1 sec
Approaches
Approach:
- First, we must calculate the ‘f(x)’ for all x in the range ‘[1, N]’, both inclusive.
- To do so, we can form an array ‘phi’ of length ‘N+1’ where ‘phi[i]’ = ‘f(i)’.
- We can run a nested loop to calculate the array Phi.
- For ‘i’ the range ‘[1, N]’ both inclusive
- ‘phi[i]’ = ‘0’.
- For every ‘j’ in the range ‘[1,i+1]’
- Increment ‘phi[i]’ if ‘gcd(j, i)==1’
- Now we have to make a vector of prime numbers dividing for all integers from 1 to ‘N’.
- To do this, we can use a similar technique of the Sieve of Eratosthenes to store the divisible prime numbers.
- Now, if we see ‘2*3*5*7*11*13*17’ = ‘510510’, which is greater than ‘100000’, any number less than or equal to ‘100000’ will have a maximum of ‘6’ different prime numbers.
- To calculate array ‘Y’, just go to all ‘i’ from 1 to ‘N’ and divide i’s prime number by ‘i’ and add the values from array ‘phi’ as stated in the question.
Algorithm:
- Initialize an integer array 'phi[N+1]'.
- Iterate from 'i' = 1 to 'i' = 'N':
- ‘phi[i]’ = 0;
- Iterate from j= ‘1’ to ‘j’=i+1
- If ‘j’ is coprime to ‘i’ increment ‘phi[i]’
- if( gcd(i,j)==1)’phi[i]’++
- Initialize an array of vectors of size ‘N+1’ ‘vector<int>primes[N+1]’ to store all prime numbers divisible by all integers from ‘1’ to ‘N’.
- Iterate from ‘i’= 2 to i= ‘N’
- if ‘i’ is prime, then it will have no prime number added to it till now.
- if( primes[i].size==0)
- Iterate from j=i to j= ‘N’ with ‘j’ increasing by ‘i’ per iteration
- Push ‘i’ to ‘primes[j]’ as i is prime and is divisible by ‘j’.
- ‘primes[j].push(i)’;
- Iterate from j=i to j= ‘N’ with ‘j’ increasing by ‘i’ per iteration
- Initialize an array ‘Y’ of length ‘N’.
- Iterate ‘i’ from ‘i’ = 0 to ‘i’ = ‘N-1’
- ‘Y[i]’ stores value of ‘g(i+1)’
- ‘Y[i]’ = ‘0’
- Iterate j from j=0 to j=primes[i+1].size()
- Int ‘z’ = ‘(i+1) / (primes[i+1][j])’
- ‘Y[i]’ += ‘phi[z]’;
- Return array ‘Y’ as the final output.
Approach:
- First, we need to calculate the ‘f(x)’ for all ‘x’ in the range ‘[1, N]’, both inclusive.
- To do so, we can form an array ‘phi’ of length ‘N+1’ where ‘phi[i] = f(i)’.
- Using the Euler totient function, we can calculate the number of coprime to a number less than equal to it. We will use the divisor sum property of the Euler totient function to find all values of ‘phi’ in O(NlogN) time.
- You can refer to the explanation and code here: https://cp-algorithms.com/algebra/phi-function.html.
- So now we are just left to check ‘gcd(x,x+1)’ for all positive integers less than equal to ‘N’, But ‘gcd(x,x+1)’ = ‘gcd(x,(x+1-x))’ = ‘1’, so ‘x+1’ is always coprime to ‘x’ ( where x is a positive integer).
- So we just need to calculate ‘f(x)’ value for all x from 1 to ‘N’ and store these values in array ‘phi’, which we can get using the Euler totient function in O(NlogN) time and increase the value of all of the index of ‘phi’ by ‘1’.
- Now we have to make a vector of prime numbers for all integers from ‘1’ to ‘N’, dividing them.
- To do this, we can use a similar technique of the Sieve of Eratosthenes to store the divisible prime numbers.
- Now, if we see ‘2*3*5*7*11*13*17’ = ‘510510’ > ‘100000’, any number less than ‘100000’ will have maximum ‘6’ different prime numbers.
- To calculate array ‘Y’, just go to all ‘i’ from 1 to ‘N’ and divide i’s prime number by ‘i’ and add the values from array ‘phi’ as stated in the question.
Algorithm:
- Initialize an integer array 'phi[N+1]’.
- Calculate phi using the Euler totient function.
- Since the Euler totient function only computes the number of co-primes to the number which is less than or equal to that number. So we need to add ‘1’ to every index of ‘phi’ to compute co-primes till the required limit i.e. the number plus ‘1’.
- Iterate over phi from ‘i’ =1 to i=’N’
- Increase the ‘phi[i]’ value by ‘1’.
- Initialize an array of vectors of size ‘N+1’ ‘vector<int>primes[N+1]’ to store all prime numbers divisible by all integers from ‘1’ to ‘N’.
- Iterate from ‘i’= 2 to i= ‘N’
- if ‘i’ is prime, then it will have no prime number added to it till now.
- if( primes[i].size==0)
- Iterate from j=i to j= ‘N’ with ‘j’ increasing by ‘i’ per iteration
- Push ‘i’ to ‘primes[j]’ as i is prime and is divisible by ‘j’.
- ‘primes[j].push(i)’;
- Iterate from j=i to j= ‘N’ with ‘j’ increasing by ‘i’ per iteration
- Initialize an array ‘Y’ of length ‘N’.
- Iterate ‘i’ from ‘i’ = 0 to ‘i’ = ‘N-1’
- ‘Y[i]’ stores value of ‘g(i+1)’
- ‘Y[i]’ = ‘0’
- Iterate j from j=0 to j=primes[i+1].size()
- int ‘z’ = ‘(i+1) / (primes[i+1][j])’
- As stated in the question, we need to add all these ‘z’s to the ‘Y[i]’.
- ‘Y[i]’ += ‘phi[z]’;
- Return array ‘Y’ as the final output.