Ғалбери Эратосфен
Дар бораи ҷумбонидани Эратосфен маълумот гиред
Муқаддима
Ба мо диапазони ададҳо дода шудааст ва мо бояд ҳамаи ададҳои соддаро дар ин диапазон пайдо кунем.
Масалан, дар диапазони
ададҳои содда инҳоянд:
Дар бораи ҷумбонидани Эратосфен маълумот гиред
Ба мо диапазони ададҳо дода шудааст ва мо бояд ҳамаи ададҳои соддаро дар ин диапазон пайдо кунем.
Масалан, дар диапазони
ададҳои содда инҳоянд:
Алгоритми классикӣ барои ин вазифа Элаккунии Эратосфен мебошад.
Ҳангоми коркарди ададҳо дар диапазон, мо метавонем фавран ҳамаи зарбҳои адади соддаи ҷориро ҳамчун мураккаб қайд кунем.
Масалан:
2-ро коркард мекунем, метавонем ҳамаи зарбҳои 2-ро ҳамчун мураккаб қайд кунем;3-ро коркард мекунем, метавонем ҳамаи зарбҳои 3-ро ҳамчун мураккаб қайд кунем;Ин ба мо имкон медиҳад, ки тадриҷан ҳамаи ададҳои ғайрисоддаро хориҷ кунем.
Як далели муҳимро ба ёд оред: агар ададе мураккаб бошад, пас он тақсимкунандаи соддае дорад, ки аз калон нест.
Аз ин рӯ, барои ёфтани ҳамаи ададҳои содда то , кофист, ки раванди элаккуниро танҳо бо ададҳо то иҷро кунем.
Мо массиви prime-ро месозем, ки дар он:
prime[x] = true маънои онро дорад, ки x ҳоло содда ҳисобида мешавад;prime[x] = false маънои онро дорад, ки x мураккаб аст.Дар оғоз, ҳамаи ададҳо ба ҷуз 0 ва 1 ҳамчун содда қайд карда мешаванд.
Сипас барои ҳар як адади i аз 2 то :
i ҳанӯз ҳамчун содда қайд шуда бошад, пас ҳамаи зарбҳои i-ро ҳамчун мураккаб қайд кунед.Даври дохилӣ аз оғоз мешавад, зеро ҳамаи зарбҳои хурдтари аллакай пештар коркард шудаанд.
Масалан, агар мо дар i = 5 бошем, пас:
10 = 2 \cdot 5 аллакай ҳангоми коркарди 2 қайд шудааст;15 = 3 \cdot 5 аллакай ҳангоми коркарди 3 қайд шудааст;20 = 4 \cdot 5 ҳатто боз ҳам пештар қайд шудааст.Пас аввалин зарби наве, ки бояд қайд кунем, аст.
Дар баъзе масъалаҳо, қимати метавонад аз ҳадди навъи int зиёд шуда overflow кунад.
Дар чунин ҳолатҳо, бехатартар аст, ки пеш аз зарбкунӣ i-ро ба long long табдил диҳем.
Масалан:
int n;
vector<bool> prime(n + 1, true);
prime[0] = prime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (prime[i]) {
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}
for (int i = 2; 1LL * i * i <= n; ++i) {
...
}