Шугаман шигшүүр¶

$n$ тоо өгөгдсөн үед $[2;n]$ хэрчим дэх бүх анхны тоог ол.

Энэ бодлогыг бодох стандарт арга бол Эратосфены шигшүүр-ийг ашиглах явдал юм. Энэ алгоритм маш энгийн боловч $O(n \log \log n)$ ажиллах хугацаатай.

Шугамаас доош ажиллах хугацаатай (өөрөөр хэлбэл $o(n)$) олон алгоритм мэдэгдэж байгаа ч доор тайлбарласан алгоритм энгийн байдлаараа сонирхолтой: энэ нь сонгодог Эратосфены шигшүүрээс илүү төвөгтэй биш юм.

Түүнчлэн энд өгөгдсөн алгоритм нь дайвар үр дүн болгон $[2; n]$ хэрчим дэх бүх тооны үржигдэхүүнд задаргааг тооцоолох ба энэ нь олон практик хэрэглээнд тустай байж болно.

Энэ алгоритмын сул тал нь сонгодог Эратосфены шигшүүрээс илүү их санах ой ашигладагт оршино: энэ нь $n$ тооны массив шаарддаг бол сонгодог Эратосфены шигшүүрт $n$ бит санах ой (32 дахин бага) байхад хангалттай.

Тиймээс тайлбарласан алгоритмыг зөвхөн $10^7$ орчим эрэмбийн тоо хүртэл ашиглах нь утга учиртай бөгөөд түүнээс их биш.

Алгоритм нь Пол Причардынх юм. Энэ нь (Pritchard, 1987: өгүүллийн төгсгөл дэх эх сурвалжийг үзнэ үү) бүтээл дэх Алгоритм 3.3-ын хувилбар юм.

Алгоритм¶

Бидний зорилго бол $[2; n]$ хэрчим дэх тоо $i$ бүрийн хувьд хамгийн бага анхны үржигдэхүүн $lp [i]$-г тооцоолох явдал юм.

Түүнчлэн бид олдсон бүх анхны тооны жагсаалтыг хадгалах хэрэгтэй — үүнийг $pr []$ гэж нэрлэе.

Бид $lp [i]$ утгуудыг тэгээр эхлүүлнэ, энэ нь бүх тоог анхны гэж үзэж байна гэсэн үг. Алгоритм ажиллах явцад энэ массив аажмаар дүүрнэ.

Одоо бид 2-оос $n$ хүртэлх тоонуудыг давтана. Одоогийн тоо $i$-гийн хувьд бидэнд хоёр тохиолдол байна:

$lp[i] = 0$ — энэ нь $i$ анхны тоо гэсэн үг, өөрөөр хэлбэл бид түүнд ямар ч бага үржигдэхүүн олоогүй байна. Тиймээс бид $lp [i] = i$ гэж оноож, $i$-г $pr[]$ жагсаалтын төгсгөлд нэмнэ.
$lp[i] \neq 0$ — энэ нь $i$ нийлмэл бөгөөд түүний хамгийн бага анхны үржигдэхүүн нь $lp [i]$ гэсэн үг.

Хоёр тохиолдолд ч бид $i$-д хуваагддаг тоонуудын $lp []$ утгыг шинэчилнэ. Гэвч бидний зорилго бол тоо бүрийн хувьд $lp []$ утгыг хамгийн ихдээ нэг удаа тавихаар хийж сурах явдал юм. Үүнийг дараах байдлаар хийж болно:

$x_j = i \cdot p_j$ тоонуудыг авч үзье, энд $p_j$ нь $lp [i]$-ээс бага буюу тэнцүү бүх анхны тоо (иймээс л бид бүх анхны тооны жагсаалтыг хадгалах шаардлагатай).

Бид энэ хэлбэрийн бүх тооны хувьд шинэ утга $lp [x_j] = p_j$ гэж тавина.

Энэ алгоритмын зөв болохын баталгаа болон ажиллах хугацааг хэрэгжүүлэлтийн дараа олж болно.

Implementation¶

const int N = 10000000;
vector<int> lp(N+1);
vector<int> pr;

for (int i=2; i <= N; ++i) {
    if (lp[i] == 0) {
        lp[i] = i;
        pr.push_back(i);
    }
    for (int j = 0; i * pr[j] <= N; ++j) {
        lp[i * pr[j]] = pr[j];
        if (pr[j] == lp[i]) {
            break;
        }
    }
}

Зөв болохын баталгаа¶

Бид алгоритм бүх $lp []$ утгыг зөв тавьдаг бөгөөд утга бүр яг нэг удаа тавигдана гэдгийг батлах хэрэгтэй. Тиймээс алгоритмын үлдсэн бүх үйлдэл мэдээж $O (n)$-д ажилладаг тул алгоритм шугаман ажиллах хугацаатай болно.

Тоо $i$ бүр дараах хэлбэрийн яг нэг илэрхийлэлтэй болохыг анхаараарай:

$$i = lp [i] \cdot x,$$

энд $lp [i]$ нь $i$-гийн хамгийн бага анхны үржигдэхүүн бөгөөд $x$ тоо нь $lp [i]$-ээс бага ямар ч анхны үржигдэхүүнгүй, өөрөөр хэлбэл

$$lp [i] \le lp [x].$$

Одоо үүнийг бидний алгоритмын үйлдэлтэй харьцуулъя: үнэндээ $x$ бүрийн хувьд алгоритм дээрх хэлбэрийн тоог гаргахын тулд түүнийг үржүүлж болох бүх анхны тоо, өөрөөр хэлбэл $lp [x]$ хүртэлх (түүнийг оруулаад) бүх анхны тоог давтана.

Тиймээс алгоритм нийлмэл тоо бүрийг яг нэг удаа давж, тэнд зөв $lp []$ утгыг тавина. Баталгаа дууслаа.

Ажиллах хугацаа ба санах ой¶

$O(n)$ ажиллах хугацаа нь сонгодог Эратосфены шигшүүрийн $O(n \log \log n)$-ээс сайн боловч тэдгээрийн ялгаа тийм ч том биш. Практикт шугаман шигшүүр нь Эратосфены шигшүүрийн ердийн хэрэгжүүлэлттэй ойролцоо хурдтай ажилладаг.

Эратосфены шигшүүрийн оновчилсон хувилбар, тухайлбал хэсэгчилсэн шигшүүртэй харьцуулбал энэ нь хамаагүй удаан.

Энэ алгоритмын санах ойн шаардлагыг харгалзан үзвэл — $n$ урттай $lp []$ массив ба $\frac n {\ln n}$ урттай $pr []$ массив — энэ алгоритм сонгодог шигшүүрээс бүх талаараа муу мэт харагдана.

Гэвч түүний гавьяа нь энэ алгоритм $lp []$ массивыг тооцоолдогт оршино, энэ нь $[2; n]$ хэрчим дэх дурын тооны үржигдэхүүнд задаргааг тухайн задаргааны хэмжээний эрэмбийн хугацаанд олох боломж олгодог. Түүнчлэн ганц нэмэлт массив ашигласнаар үржигдэхүүнд задаргаа хайхад хуваалтаас зайлсхийх боломжтой.

Бүх тооны үржигдэхүүнд задаргааг мэдэх нь зарим бодлогод маш хэрэгтэй бөгөөд энэ алгоритм нь тэдгээрийг шугаман хугацаанд олох боломж олгодог цөөн алгоритмын нэг юм.

Эх сурвалж¶

Paul Pritchard, Linear Prime-Number Sieves: a Family Tree, Science of Computer Programming, vol. 9 (1987), pp.17-35.