1bool isPrime(int n) {
2    if (n < 2) return false;
3    for (int i = 2; i * i <= n; i++)
4        if (n % i == 0) return false;
5    return true;
6}

1bool notPrime[N];
2void sieve(int n) {
3    notPrime[0] = notPrime[1] = true;
4    for (int i = 2; i * i <= n; i++)
5        if (!notPrime[i])
6            for (int j = i * i; j <= n; j += i)
7                notPrime[j] = true;
8}

1int primes[N], cnt = 0;
2bool notPrime[N];
3void linearSieve(int n) {
4    for (int i = 2; i <= n; i++) {
5        if (!notPrime[i]) primes[cnt++] = i;
6        for (int j = 0; j < cnt && i * primes[j] <= n; j++) {
7            notPrime[i * primes[j]] = true;
8            if (i % primes[j] == 0) break;
9        }
10    }
11}