New update is available. Click here to update.

Solve problems & track your progress

Checkout your overall progress in every topic here

Become

Sensei

in DSA topics

Open the topic and solve more problems associated with it to improve your skills

Check out the skill meter for every topic

See how many problems you are left with to solve for cracking any stage. Score more than zero to get your progress counted.

Problem

Submissions

Co-Prime

Contributed by

Piyush Sharma

Last Updated: 23 Feb, 2023

Hard

0/120

Avg time to solve 30 mins

Success Rate 30 %

0 upvotes

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 )

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

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

Auto

Console