Sieve of Eratosthenes

Testing every integer independently repeats divisibility work. Eratosthenes instead preprocesses an entire bounded range, marking multiples of each discovered prime. After one sieve, primality queries are constant-time and the ordered prime list is available for later algorithms. The main idea is eliminating known composites, not trying every possible divisor for every number.

Prerequisites: Prime Numbers and Primality Testing; arrays.

Build the idea

1. 1. Initialize the meaning of a mark

   Create isPrime[0..N], initially true except 0 and 1 when present. A true entry means “not yet shown composite” during construction, and “prime” only after the sieve completes. Zero and one are not primes; small N must not cause writes beyond the allocated vector.

2. 2. Process candidate primes in increasing order

   For p from 2 through √N, skip it if already marked composite. Otherwise p has no smaller prime divisor and is prime. Mark p²,p²+p,… . Any multiple k·p with k<p already has a prime factor below p and was handled earlier. Starting at p rather than p² would incorrectly mark p itself.

   $$j=p^2,p^2+p,p^2+2p,\dots$$

3. 3. Prove every composite is removed

   A composite m≤N has a prime factor p≤√m≤√N. When p is processed, m is one of its multiples and is at least p² if p is its smallest prime factor. Therefore it is marked. A prime is never a nontrivial multiple of a smaller prime, so it stays true. This establishes both directions of the final table’s meaning.

4. 4. Trace N=20

   For p=2 mark 4,6,8,10,12,14,16,18,20. For p=3 start at 9 and mark 9,12,15,18. Candidate 4 is already composite and no candidate above √20 needs processing. Remaining primes are 2,3,5,7,11,13,17,19. Queries 1,2,18,19 become NO,YES,NO,YES.

5. 5. Understand memory and scaling

   A byte-per-flag vector makes memory usage easy to reason about; vector<bool> typically packs bits with proxy-reference behavior, and odd-only storage can nearly halve a simple table. These are representation optimizations, not different prime definitions. For a huge interval near a large number, a segmented sieve stores only a block and uses base primes; this full-range implementation instead requires N itself to fit memory.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Understand memory and scaling A byte-per-flag vector makes memory usage easy to reason
// about; vector<bool> typically packs bits with proxy-reference behavior, and odd-only storage can
// nearly halve a simple table.
#include<iostream>
#include<vector>
int main(){
    int N,q;
    std::cin>>N>>q;
    std::vector<char>isPrime(N+1,true);
    isPrime[0]=false;
    if(N>=1){
        isPrime[1]=false;
    }
    for(int p=2;p<=N/p;++p){
        if(isPrime[p]){
            for(long long multiple=1LL*p*p;multiple<=N;multiple+=p){
                isPrime[(int)multiple]=false;
            }
        }
    }
    bool first=true;
    for(int p=2;p<=N;++p){
        if(isPrime[p]){
            if(!first){
                std::cout<<' ';
            }
            std::cout<<p;
            first=false;
        }
    }
    std::cout<<'\n';
    while(q--){
        int x;
        std::cin>>x;
        std::cout<<(isPrime[x]?"YES":"NO")<<'\n';
    }
}

Complexity analysis

O(N log log N) preprocessing time for N≥3 and O(N) space; O(1) per primality query, plus O(N) scanning to print primes. Summing marking work over primes gives the log-log factor, sharper than summing N/p over all integers. Small N is handled directly.

Example input and output

Read N q (0≤N≤10^7, q≥0), then q integers in 0..N. Print all primes≤N on one line (possibly blank), then YES/NO for each query.

Input

20 4
1
2
18
19

Output

2 3 5 7 11 13 17 19
NO
YES
NO
YES

Marking multiples of 2 and 3 removes every composite≤20; 1 is separately excluded.

Practical applications

Use for many moderate-range prime queries, prime lists, factorization preprocessing and number-theory tables. Trial division is simpler for a few isolated values. SPF tables add factor information at a larger per-entry memory cost.

Check your understanding

Why may marking begin at p²?

Put it into practice

Test N=0,1,2 and compare against trial division.