Γραμμικό κόσκινο
Οι πρώτοι μέχρι το και ο μικρότερος πρώτος διαιρέτης κάθε αριθμού σε . Μετά, παραγοντοποίηση σε .
Πότε
Πολλοί αριθμοί έως ή που πρέπει να παραγοντοποιηθούν, ή μια συνάρτηση όπως το πλήθος διαιρετών ή η για όλους τους αριθμούς μέχρι το .
Η ιδέα
Κάθε σύνθετος γράφεται μοναδικά ως , όπου ο μικρότερος πρώτος διαιρέτης του . Τότε . Για κάθε , διατρέχουμε τους πρώτους και θέτουμε . Κάθε σύνθετος σημειώνεται ακριβώς μία φορά, άρα .
Το κόσκινο του Ερατοσθένη είναι και σχεδόν το ίδιο γρήγορο. Το γραμμικό αξίζει επειδή δίνει δωρεάν τον πίνακα . Με αυτόν, η παραγοντοποίηση του είναι «διαίρει με το μέχρι να φτάσεις στο 1», το πολύ βήματα.
Πλήθος διαιρετών
Αν , το πλήθος των διαιρετών είναι . Στο Counting Divisors ( αριθμοί έως ) αυτό είναι ένα factorize ανά αριθμό.
Παγίδες
- Ο πίνακας για είναι 40 MB σε
int. Για είναι αμελητέος. - Ο έλεγχος
(ll)p * i > nγίνεται σεlong long: για κοντά στο το γινόμενο σεintυπερχειλίζει. - Το test συγκρίνει με δοκιμαστική διαίρεση όλους τους αριθμούς ως το , και ελέγχει ότι .
Κώδικας
Χωρίς main: μπαίνει κάτω από τα #include, το using namespace std και το using ll = long long.
// 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
Με τη σειρά: το πρώτο είναι η καθαρή εφαρμογή, τα επόμενα θέλουν μια παραλλαγή.
- Counting Divisors · Mathematics
- Common Divisors · Mathematics
Περισσότερα στο USACO Guide
- Divisibility · usaco.guide/gold/divisibility
Στα αγγλικά, με επιπλέον προβλήματα ανά επίπεδο.