Hide

# Prime Sieve

## Input

The first line of input consists of two integers $n$, $q$, where $1 \leq n \leq 10^8$ and $1 \leq q \leq 20000$. Then follow $q$ lines, each containing an integer $x$ satisfying $1 \leq x \leq n$.

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

CPU Time limit
2 seconds

Memory limit
50 MB

Statistics
Show

Downloads

Author

Per Austrin

Source
KTH CSC Popup 2005