uniolympiads English

Γραμμικό κόσκινο

Οι πρώτοι μέχρι το nn και ο μικρότερος πρώτος διαιρέτης κάθε αριθμού σε O(n)O(n). Μετά, παραγοντοποίηση σε O(log⁡x)O(\log x).

Πότε

Πολλοί αριθμοί έως 10610^6 ή 10710^7 που πρέπει να παραγοντοποιηθούν, ή μια συνάρτηση όπως το πλήθος διαιρετών ή η φ\varphi για όλους τους αριθμούς μέχρι το nn.

Η ιδέα

Κάθε σύνθετος xx γράφεται μοναδικά ως x=p⋅ix = p \cdot i, όπου pp ο μικρότερος πρώτος διαιρέτης του xx. Τότε p≤spf(i)p \le \mathrm{spf}(i). Για κάθε ii, διατρέχουμε τους πρώτους p≤spf(i)p \le \mathrm{spf}(i) και θέτουμε spf(p⋅i)=p\mathrm{spf}(p \cdot i) = p. Κάθε σύνθετος σημειώνεται ακριβώς μία φορά, άρα O(n)O(n).

Το κόσκινο του Ερατοσθένη είναι O(nlog⁡log⁡n)O(n \log \log n) και σχεδόν το ίδιο γρήγορο. Το γραμμικό αξίζει επειδή δίνει δωρεάν τον πίνακα spf\mathrm{spf}. Με αυτόν, η παραγοντοποίηση του xx είναι «διαίρει με το spf(x)\mathrm{spf}(x) μέχρι να φτάσεις στο 1», το πολύ log⁡2x\log_2 x βήματα.

Πλήθος διαιρετών

Αν x=p1e1⋯pkekx = p_1^{e_1} \cdots p_k^{e_k}, το πλήθος των διαιρετών είναι (e1+1)⋯(ek+1)(e_1 + 1) \cdots (e_k + 1). Στο Counting Divisors (10510^5 αριθμοί έως 10610^6) αυτό είναι ένα factorize ανά αριθμό.

Παγίδες

  • Ο πίνακας spf\mathrm{spf} για n=107n = 10^7 είναι 40 MB σε int. Για 10610^6 είναι αμελητέος.
  • Ο έλεγχος (ll)p * i > n γίνεται σε long long: για nn κοντά στο 2312^{31} το γινόμενο σε int υπερχειλίζει.
  • Το test συγκρίνει με δοκιμαστική διαίρεση όλους τους αριθμούς ως το 10510^5, και ελέγχει ότι π(105)=9592\pi(10^5) = 9592.

Κώδικας

Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.

cpp/sieve.cpp
// Linear sieve: primes up to n and the smallest prime factor of every number. O(n).
// Every composite x is crossed out exactly once, by its smallest prime factor.
// factorize(x) then runs in O(log x) for x <= n.

struct Sieve {
    vector<int> spf;
    vector<int> primes;

    Sieve(int n) : spf(n + 1, 0) {
        for (int i = 2; i <= n; i++) {
            if (spf[i] == 0) {
                spf[i] = i;
                primes.push_back(i);
            }
            for (int p : primes) {
                if (p > spf[i] || (ll)p * i > n) {
                    break;
                }
                spf[p * i] = p;
            }
        }
    }

    bool isPrime(int x) {
        return x >= 2 && spf[x] == x;
    }

    // (prime, exponent) pairs in increasing order of the prime.
    vector<pair<int, int>> factorize(int x) {
        vector<pair<int, int>> f;
        while (x > 1) {
            int p = spf[x];
            int e = 0;
            while (x % p == 0) {
                x /= p;
                e++;
            }
            f.push_back({p, e});
        }
        return f;
    }
};

Ελέγχθηκε σε 100.001 τυχαίες περιπτώσεις απέναντι σε αργή, προφανώς σωστή λύση, με AddressSanitizer και UndefinedBehaviorSanitizer (g++ (Ubuntu 13.3.0-6ubuntu2~24.04.1) 13.3.0, 2026-11-18 23:27 UTC).

Για εξάσκηση στο CSES

Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.

Περισσότερα στο USACO Guide

Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.