kz-maxx

RU KZ
← Басты бет

Эратосфен решетосы

n-ге дейінгі барлық жай сандарды тез табатын алгоритм

Жай сан деген не?

Жай сан — 1-ден үлкен және тек 1-ге және өзіне ғана бөлінетін сан.

Жай сандар мысалы: 

2 3 5 7 11 13 17 19

Мысалы, 7 жай сан, себебі ол тек 1 және 7-ге бөлінеді.

Құрама сан деген не?

Құрама сан — 1-ден үлкен және 1 мен өзінен басқа бөлгіші бар сан.

Құрама сандар мысалы: 

4 6 8 9 10 12 14 15

Мысалы, 12 құрама сан, себебі ол мына сандарға бөлінеді: 

1 2 3 4 6 12
1 саны жай сан да емес, құрама сан да емес.

Задача

n саны берілген. 1-ден n-ге дейінгі барлық жай сандарды табу керек.

Input

20

Output

2 3 5 7 11 13 17 19

Баяу әдіс

Әр санды жеке-жеке тексеруге болады: жай ма, жай емес пе.

x санын тексеру: 

bool is_prime(int x) {
    if (x < 2) {
        return false;
    }

    for (int d = 2; d * d <= x; d++) {
        if (x % d == 0) {
            return false;
        }
    }

    return true;
}

Егер барлық санды 1-ден n-ге дейін осылай тексерсек:

O(n√n)
n үлкен болса, бұл метод баяу болуы мүмкін.

Эратосфен решетосының идеясы

Әр санды бөлек тексермейміз. Оның орнына құрама сандарды белгілеп шығамыз.

Идея:

1. Басында барлық санды жай деп ойлаймыз
2. Бірінші жай сан p аламыз
3. p-ның барлық кратный сандарын құрама деп белгілейміз
4. Келесі белгіленбеген санға өтеміз

Мысалы, егер p = 2, онда белгілейміз: 

4 6 8 10 12 14 16 ...

Егер p = 3, онда белгілейміз: 

6 9 12 15 18 21 ...

Не сақтаймыз?

Массив құрамыз: 

isPrime[i]

Мағынасы:

  • true — i саны әзірше жай деп саналады
  • false — i саны құрама

Басында барлық санды жай деп қоямыз: 

vector<bool> isPrime(n + 1, true);

Бірақ 0 және 1 жай сан емес: 

isPrime[0] = false;
isPrime[1] = false;

Негізгі цикл

p санын перебор жасаймыз. Егер ол әлі жай болса, оның кратный сандарын белгілейміз. 

for (int p = 2; p * p <= n; p++) {
    if (isPrime[p]) {
        for (int x = p * p; x <= n; x += p) {
            isPrime[x] = false;
        }
    }
}
Ішкі цикл p * p-дан басталады. Себебі одан кіші кратный сандар бұрын белгіленіп кеткен.

Неге p * p-дан бастаймыз?

Мысалы, p = 5. 5-тің кратный сандары: 

10 15 20 25 30 35 ...

Бірақ:

  • 10 санын 2 белгілеп қойған
  • 15 санын 3 белгілеп қойған
  • 20 санын 2 белгілеп қойған

5 үшін нақты басталатын бірінші жаңа сан: 

25 = 5 * 5
сондықтан p * p-дан бастаймыз

Неге сыртқы цикл sqrt(n)-ге дейін?

Егер x құрама сан болса, оның бір бөлгіші міндетті түрде sqrt(x)-тен аспайды.

Сондықтан n-ге дейінгі барлық құрама санды белгілеу үшін p-ны тек sqrt(n)-ге дейін қарау жеткілікті. 

p * p <= n

Осыдан кейін белгіленбей қалған сандар жай болады.

Эратосфен решетосының толық реализациясы

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<bool> isPrime(n + 1, true);

    if (n >= 0) {
        isPrime[0] = false;
    }

    if (n >= 1) {
        isPrime[1] = false;
    }

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int x = p * p; x <= n; x += p) {
                isPrime[x] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            cout << i << ' ';
        }
    }

    return 0;
}

Input / Output

Input

30

Output

2 3 5 7 11 13 17 19 23 29

Решето қолмен қалай жұмыс істейді?

n = 20 болсын.

Басында: 

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2-ні аламыз, кратный сандарын белгілейміз: 

4 6 8 10 12 14 16 18 20

3-ті аламыз, кратный сандарын белгілейміз: 

9 15

5-ке келгенде: 5 * 5 = 25, ол 20-дан үлкен.

Қалған жай сандар: 

2 3 5 7 11 13 17 19

Жай сандар санын табу коды

Кейде жай сандарды шығармай, тек санын табу керек. 

int cnt = 0;

for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
        cnt++;
    }
}

cout << cnt;

Толық код: n-ге дейін қанша жай сан бар?

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<bool> isPrime(n + 1, true);

    if (n >= 0) {
        isPrime[0] = false;
    }

    if (n >= 1) {
        isPrime[1] = false;
    }

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int x = p * p; x <= n; x += p) {
                isPrime[x] = false;
            }
        }
    }

    int cnt = 0;

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            cnt++;
        }
    }

    cout << cnt;

    return 0;
}

Жай сандарды vector ішіне сақтау

Көбіне барлық жай сандарды массивке сақтап алу ыңғайлы: 

vector<int> primes;

for (int i = 2; i <= n; i++) {
    if (isPrime[i]) {
        primes.push_back(i);
    }
}

Кейін primes басқа задачаларда қолданылады.

sieve функциясы

Решетоны бөлек функцияға шығарған ыңғайлы. 

vector<int> sieve(int n) {
    vector<bool> isPrime(n + 1, true);
    vector<int> primes;

    if (n >= 0) {
        isPrime[0] = false;
    }

    if (n >= 1) {
        isPrime[1] = false;
    }

    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int x = p * p; x <= n; x += p) {
                isPrime[x] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push_back(i);
        }
    }

    return primes;
}

long long-пен қауіпсіз вариант

Егер n үлкен болса, p * p int ішінде overflow беруі мүмкін.

Сондықтан қауіпсіз жазу: 

1LL * p * p <= n

Ішкі циклдің стартын да былай жазамыз: 

for (long long x = 1LL * p * p; x <= n; x += p)

Қауіпсіз реализация

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<bool> isPrime(n + 1, true);

    if (n >= 0) {
        isPrime[0] = false;
    }

    if (n >= 1) {
        isPrime[1] = false;
    }

    for (int p = 2; 1LL * p * p <= n; p++) {
        if (isPrime[p]) {
            for (long long x = 1LL * p * p; x <= n; x += p) {
                isPrime[x] = false;
            }
        }
    }

    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            cout << i << ' ';
        }
    }

    return 0;
}

Smallest Prime Factor

Кейде сан жай ма емес пе ғана емес, сандарды тез простые множители-ге жіктеу керек болады.

Онда мына массивті санаймыз: 

spf[x]

spf[x] — smallest prime factor, яғни x санының ең кіші жай бөлгіші.

spf[12] = 2
spf[15] = 3
spf[17] = 17

SPF коды

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;

int spf[N + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i <= N; i++) {
        spf[i] = i;
    }

    for (int p = 2; p * p <= N; p++) {
        if (spf[p] == p) {
            for (int x = p * p; x <= N; x += p) {
                if (spf[x] == x) {
                    spf[x] = p;
                }
            }
        }
    }

    int x;
    cin >> x;

    while (x > 1) {
        cout << spf[x] << ' ';
        x /= spf[x];
    }

    return 0;
}

SPF мысалы

Input

60

Output

2 2 3 5

Себебі: 

60 = 2 * 2 * 3 * 5

Көп query үшін решето

Кейде көп запрос болады: әр сан жай ма, жоқ па тексеру керек.

Онда решетоны бір рет жасап аламыз, кейін әр query-ге O(1) жауап береміз. 

if (isPrime[x]) {
    cout << "YES";
} else {
    cout << "NO";
}

Query-мен толық код

#include <bits/stdc++.h>
using namespace std;

const int N = 1000000;

bool isPrime[N + 1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i <= N; i++) {
        isPrime[i] = true;
    }

    isPrime[0] = false;
    isPrime[1] = false;

    for (int p = 2; p * p <= N; p++) {
        if (isPrime[p]) {
            for (int x = p * p; x <= N; x += p) {
                isPrime[x] = false;
            }
        }
    }

    int q;
    cin >> q;

    while (q--) {
        int x;
        cin >> x;

        if (isPrime[x]) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    return 0;
}

Асимптотика

Метод Уақыт Память
Әр санды бөлек тексеру O(n√n) O(1)
Эратосфен решетосы O(n log log n) O(n)
Решетодан кейін query answer O(1) O(n)
n-ге дейін көп жай сан керек болса, решето өте жылдам жұмыс істейді.

Решетоны қашан қолданамыз?

1. n-ге дейін барлық жай сан керек
2. isPrime[x] query-леріне тез жауап беру керек
3. Көп санды множительдерге жіктеу керек
4. n-ге дейін жай сандар санын табу керек
5. primes list-ін басқа задачада қолдану керек

Типтік қателер

  • 1 санын жай сан деп ойлау
  • isPrime[0] = false қоюды ұмыту
  • isPrime[1] = false қоюды ұмыту
  • Ішкі циклді p * p орнына 2 * p-дан бастау
  • p * p ішінде overflow алу
  • Тек бір кішкентай сан тексеру керек кезде решето қолдану
  • Массив size-ын тым кішкентай жасау

Қысқа шаблон

vector<bool> isPrime(n + 1, true);

if (n >= 0) {
    isPrime[0] = false;
}

if (n >= 1) {
    isPrime[1] = false;
}

for (int p = 2; 1LL * p * p <= n; p++) {
    if (isPrime[p]) {
        for (long long x = 1LL * p * p; x <= n; x += p) {
            isPrime[x] = false;
        }
    }
}