Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Co-Prime

Hard
0/120
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
TCS

Problem statement

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’.
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
1 <= T <= 10
1 <= N <= 10^5


Time Limit: 1 sec
Sample Input 1 :
2
4
5
Sample Output 1 :
0 2 2 2
0 2 2 2 2   
Explanation Of Sample Input 1 :
For test case 1:
First, calculate ‘f(1)’, ‘f(2)’ and ‘f(3)’.
‘f(1)’ = ‘2’ as ‘1’ and ‘2’ are coprime to ‘1’.
‘f(2)’ = ‘2’ as ‘1’ and ‘3’ are coprime to ‘2’.
‘f(3)’ = ‘3’ as ‘1’, ‘2’  and ‘4’ are coprime to ‘3’.
Now calculate ‘g(1)’ , ‘g(2)’, ‘g(3)’.
‘g(1)’ as there is no prime number that 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’.
‘g(4)’ = ‘f(4/2)’ = ‘f(2)’ = ‘2’  as ‘2’ is the only prime number that divides ‘4’.




For test case 2:
First calculate ‘f(1)’, ‘f(2)’ and ‘f(3)’.
‘f(1)’ = ‘2’ as ‘1’ and ‘2’ are coprime to ‘1’.
‘f(2)’ = ‘2’ as ‘1’ and ‘3’ are coprime to ‘2’.
‘f(3)’ = ‘3’ as ‘1’, ‘2’  and ‘4’ are coprime to ‘3’.
Now calculate ‘g(1)’ , ‘g(2)’, ‘g(3)’.
‘g(1)’ as there is no prime number that 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’.
‘g(4)’ = ’f(4/2)’ = ‘f(2)’ = ‘2’ as ‘2’ is the only prime number that divides ‘4’.
‘g(5)’ = ‘f(5/5)’ = ‘f(1)’ = ‘2’ as ‘5’ is the only prime number that divides ‘5’.
Sample Input 2 :
2
6 
7 
Sample Output 2 :
0 2 2 2 2 5
0 2 2 2 2 5 2
Full screen
Console