Hide

Problem G
Prime Sieve

Input

The first line of input consists of two integers n, q, where 1n108 and 1q20000. Then follow q lines, each containing an integer x satisfying 1xn.

Output

On the first line of output, write one line giving the number of prime numbers less than or equal to n. Then for each query x, output 1 if x is a prime and ouput 0 if x is composite.

Sample Input 1 Sample Output 1
9973 6
1
2
3
4
9972
9973
1229
0
1
1
0
0
1
Hide

Please log in to submit a solution to this problem

Log in