5730. YAPTCHA

 

The Faculty of Mathematics encountered a problem. Due to the large number of automated programs browsing their web pages, it was decided to restrict access to their scientific articles.

To gain access, one must now demonstrate their knowledge – namely, solve a mathematical problem.

However, the test turned out to be too difficult not only for graduate students, but even for some professors. Therefore, the faculty needs to develop a program that automatically solves this problem.

Visitors to the main page of the Faculty of Mathematics are given the following task: for a given positive integer n, compute the value

Sn =

where ⌊x⌋ denotes the greatest integer less than or equal to x.

 

Input. The first line contains the number of queries t (t ≤ 106).

Each of the following t lines contains one integer n (1 ≤ n ≤ 106).

 

Output. For each query, print the value of Sn on a separate line.

 

Sample input

Sample output

13

1

2

3

4

5

6

7

8

9

10

100

1000

10000

0

1

1

2

2

2

2

3

3

4

28

207

1609

 

 

SOLUTION

sieve of Eratosthenes

 

Algorithm analysis

Let m = 3k + 7. Then the given expression can be rewritten in the form:

Sn =

 

Wilson’s Theorem. If m is a prime number, then

(m – 1)! = -1 (mod m)

That is,

(m – 1)! + 1 = 0 (mod m)

 

Therefore, if m is prime, the number  is an integer.

At the same time,

 =  =  – 1

Then the entire expression equals

 =  –  = 1

 

If m is a composite number, then

(m – 1)! = 0 (mod m),

because among its factors there are all the divisors of m.

In this case, the number

is an integer.

Then the entire expression equals

 =  =  = 0

 

Therefore, to compute Sn, it is enough to count the number of prime numbers of the form 3k + 7 for 1 ≤ k ≤ n.

 

Using the Sieve of Eratosthenes, we build the array used, where:

Then, using the array used, construct the array a, which stores information about prime numbers of the form 3i + 7:

Now

Sn = a[1] + a[2] + … + a[n]

Since the problem contains many test cases, to answer each in constant time, we build the prefix sums:

p[i] = a[1] + a[2] + … + a[i]

Now, to solve the problem for any given value of , it is enough to print p[n].

 

Example

Let m = 7 be a prime number. Then

 =  =  =  = 1

Let m = 6 be a composite number. Then

 =  =  =  = 0

 

Let’s compute the answer for n = 10. Consider all numbers of the form 3k + 7, where 1 ≤ k ≤ 10. Among them, identify the prime numbers.

Among the listed numbers, there are 4 prime numbers: 13, 19, 31 and 37. Therefore, S10 = 4.

 

Algorithm implementation

Let us declare the arrays. Since n ≤ 106, the size of the arrays should be set to 3n + 7 = 3 * 106 + 7.

 

#define MAX 3000010

char used[MAX], a[MAX];

 

The function Init implements the Sieve of Eratosthenes. The array used stores information about prime numbers:

The array a stores information about prime numbers of the form 3i + 7:

 

void Init()

{

  for (int i = 2; i < MAX; i++)

  {

    if (!used[i])

    {

      if ((i - 7) % 3 == 0)

        a[(i - 7) / 3] = true;

      if (i < sqrt(MAX))

        for (int j = i * i; j < MAX; j += i)

          used[j] = true;

    }

  }

}

 

The main part of the program. Fill the arrays.

 

Init();

 

Compute the prefix sums for the array a:

p[i] = a1 + a2 + … + ai

 

for (int i = 2; i < MAX; ++i)

  p[i] = p[i - 1] + a[i];

 

Process the tests sequentially.

 

scanf("%d", &tests);

while (tests--)

{

  scanf("%d", &n);

 

For each value of n print p[n].

 

  printf("%d\n", p[n]);

}