Sieve of Eratosthenes

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Classic Sieve of Eratosthenes: generate primes up to n
5
// Uses vector<bool> which packs bits (bitset-like memory usage)
6
7
vector<int> sieve_primes(int n, vector<bool>& is_prime) {
8
    is_prime.assign(n + 1, true);
9
    if (n >= 0) is_prime[0] = false;
10
    if (n >= 1) is_prime[1] = false;
11
12
    // Only need to loop p up to sqrt(n)
13
    for (int p = 2; 1LL * p * p <= n; ++p) {
14
        if (is_prime[p]) {
15
            // Start at p*p to avoid redundant marking; cast to long long to prevent overflow
16
            long long start = 1LL * p * p;
17
            for (long long j = start; j <= n; j += p) {
18
                is_prime[(size_t)j] = false;
19
            }
20
        }
21
    }
22
23
    vector<int> primes;
24
    for (int i = 2; i <= n; ++i) if (is_prime[i]) primes.push_back(i);
25
    return primes;
26
}
27
28
int main() {
29
    ios::sync_with_stdio(false);
30
    cin.tie(nullptr);
31
32
    int n; // Example: input 30 -> prints primes up to 30
33
    if (!(cin >> n)) return 0;
34
35
    vector<bool> is_prime;
36
    vector<int> primes = sieve_primes(n, is_prime);
37
38
    cout << "Count = " << primes.size() << "\n";
39
    for (int p : primes) cout << p << ' ';
40
    cout << '\n';
41
    return 0;
42
}
43

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Linear sieve producing prime list and SPF (Smallest Prime Factor)
5
// Each composite is marked once as i * p where p is its smallest prime factor
6
7
struct LinearSieve {
8
    int n;
9
    vector<int> primes;  // list of primes up to n
10
    vector<int> spf;     // spf[x] = smallest prime factor of x (spf[p] = p)
11
12
    explicit LinearSieve(int n): n(n), spf(n + 1, 0) {
13
        primes.reserve(n / 10);
14
        for (int i = 2; i <= n; ++i) {
15
            if (spf[i] == 0) { // i is prime
16
                spf[i] = i;
17
                primes.push_back(i);
18
            }
19
            for (int p : primes) {
20
                long long x = 1LL * i * p;
21
                if (x > n) break;
22
                spf[(int)x] = p; // p is the smallest prime factor for x
23
                if (p == spf[i]) break; // ensure each composite is marked once
24
            }
25
        }
26
    }
27
28
    // Factorize number x (2 <= x <= n) in O(number of prime factors)
29
    vector<pair<int,int>> factorize(int x) const {
30
        vector<pair<int,int>> fac;
31
        while (x > 1) {
32
            int p = spf[x];
33
            int cnt = 0;
34
            while (x % p == 0) {
35
                x /= p;
36
                ++cnt;
37
            }
38
            fac.push_back({p, cnt});
39
        }
40
        return fac;
41
    }
42
};
43
44
int main() {
45
    ios::sync_with_stdio(false);
46
    cin.tie(nullptr);
47
48
    int N, Q; // Example: N=100, Q=3 with queries like 60 84 97
49
    if (!(cin >> N >> Q)) return 0;
50
51
    LinearSieve sieve(N);
52
    
53
    // Print primes up to N (optional)
54
    // for (int p : sieve.primes) cout << p << ' '; cout << '\n';
55
56
    while (Q--) {
57
        int x; cin >> x;
58
        auto fac = sieve.factorize(x);
59
        cout << x << " = ";
60
        for (size_t i = 0; i < fac.size(); ++i) {
61
            auto [p, c] = fac[i];
62
            cout << p;
63
            if (c > 1) cout << '^' << c;
64
            if (i + 1 != fac.size()) cout << " * ";
65
        }
66
        cout << '\n';
67
    }
68
    return 0;
69
}
70

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Segmented sieve: compute primes in [L, R] (inclusive)
5
// 1) Pre-sieve primes up to sqrt(R)
6
// 2) Mark multiples in the window [L, R]
7
8
static vector<int> base_primes_up_to(long long n) {
9
    int m = (int)n;
10
    vector<bool> is_prime(m + 1, true);
11
    if (m >= 0) is_prime[0] = false;
12
    if (m >= 1) is_prime[1] = false;
13
    for (long long p = 2; p * p <= m; ++p) if (is_prime[(size_t)p])
14
        for (long long j = p * p; j <= m; j += p)
15
            is_prime[(size_t)j] = false;
16
    vector<int> primes;
17
    for (int i = 2; i <= m; ++i) if (is_prime[i]) primes.push_back(i);
18
    return primes;
19
}
20
21
vector<long long> segmented_sieve(long long L, long long R) {
22
    if (L > R) return {};
23
    // Handle small ranges
24
    L = max(2LL, L);
25
    int sz = (int)(R - L + 1);
26
    vector<bool> is_prime_range(sz, true);
27
28
    long long root = floor(sqrt((long double)R));
29
    vector<int> primes = base_primes_up_to(root);
30
31
    for (long long p : primes) {
32
        long long start = max(p * p, ((L + p - 1) / p) * p); // first multiple in [L, R]
33
        for (long long j = start; j <= R; j += p) {
34
            is_prime_range[(size_t)(j - L)] = false;
35
        }
36
    }
37
38
    vector<long long> res;
39
    for (int i = 0; i < sz; ++i) if (is_prime_range[i]) res.push_back(L + i);
40
    return res;
41
}
42
43
int main() {
44
    ios::sync_with_stdio(false);
45
    cin.tie(nullptr);
46
47
    long long L, R; // Example: input 10 50 -> primes in [10,50]
48
    if (!(cin >> L >> R)) return 0;
49
50
    auto primes = segmented_sieve(L, R);
51
    cout << "Count = " << primes.size() << "\n";
52
    for (auto p : primes) cout << p << ' ';
53
    cout << '\n';
54
    return 0;
55
}
56

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Odd-only sieve: represent only odd numbers ≥ 3
5
// index i corresponds to number val = 2*i + 3
6
// is_comp[i] == false means the odd number is prime candidate
7
8
struct OddSieve {
9
    int n;                // upper bound
10
    vector<uint8_t> comp; // byte-per-flag (simple). Could pack further if needed.
11
12
    explicit OddSieve(int n): n(n) {
13
        int m = max(0, (n - 3) / 2 + 1); // count of odds in [3..n]
14
        comp.assign(m, 0);
15
        int limit = (int)floor(sqrt((long double)n));
16
        auto idx = [](int x){ return (x - 3) >> 1; }; // map odd x>=3 -> index
17
18
        for (int p = 3; p <= limit; p += 2) {
19
            if (p >= 3 && ((p & 1) == 1) && !comp[idx(p)]) {
20
                long long start = 1LL * p * p; // first multiple to mark
21
                if (start > n) break;
22
                // convert start (odd) to index
23
                for (long long j = start; j <= n; j += 2LL * p) {
24
                    comp[idx((int)j)] = 1;
25
                }
26
            }
27
        }
28
    }
29
30
    bool isPrime(int x) const {
31
        if (x < 2) return false;
32
        if (x == 2) return true;
33
        if ((x & 1) == 0) return false; // even > 2
34
        int i = (x - 3) >> 1;
35
        if (i < 0 || i >= (int)comp.size()) return false; // out of range
36
        return comp[i] == 0;
37
    }
38
39
    vector<int> primes() const {
40
        vector<int> res; if (n >= 2) res.push_back(2);
41
        for (int i = 0; i < (int)comp.size(); ++i) if (!comp[i]) res.push_back(2*i + 3);
42
        return res;
43
    }
44
};
45
46
int main() {
47
    ios::sync_with_stdio(false);
48
    cin.tie(nullptr);
49
50
    int n; // Example: input 100 -> primes up to 100
51
    if (!(cin >> n)) return 0;
52
53
    OddSieve S(n);
54
55
    auto ps = S.primes();
56
    cout << "Count = " << ps.size() << "\n";
57
    for (int p : ps) cout << p << ' ';
58
    cout << '\n';
59
60
    // Example prime queries
61
    int q; if (cin >> q) {
62
        while (q--) {
63
            int x; cin >> x;
64
            cout << x << (S.isPrime(x) ? " is prime" : " is not prime") << '\n';
65
        }
66
    }
67
    return 0;
68
}
69