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

Problem of the day

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’.

```
'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

```
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'.
```

```
For each test case, output the array ‘Y’.
```

```
You don’t need to print anything. It has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10
1 <= N <= 10^5
Time Limit: 1 sec
```

```
2
4
5
```

```
0 2 2 2
0 2 2 2 2
```

```
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’.
```

```
2
6
7
```

```
0 2 2 2 2 5
0 2 2 2 2 5 2
```