New update is available. Click here to update.

Topics

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

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