Анхны тоо

Анхы тоо гэдэг нь яг 2 ширхэг ялгаатай хуваагчтай натурал тоог хэлдэг. Жишээ нь 2, 3, 5, 7 гэх мэт үргэлжлээд явна.

N гэсэн тоо өгөгдөхөд тухайн тоог анхны тоо эсэхийг хэрхэн мэдэх вэ? Мэдээж бид [1, N] завсарт гүйгээд N тоог маань хэд нь хувааж байгаа вэ гэдгийг тоолоход болно. Үүнээс хурднаар шалгаж чадах уу? Анхны тоо зөвхөн 2 хуваагчтай гэхээр 1 болон өөртөө л хуваагддаг гэсэн үг ба N тоог [2, N-1] завсарт ямар ч тоо хуваадаггүй бол анхны тоо мөн. Бүр түүнчлэн N тоо нь 2-с N \sqrt N хүртэл бүх тоонд хуваагддаггүй гэвэл анхны тоо мөн байна. Учир нь N \sqrt N -с их ямар нэг хуваагч байдаг гээд X гэвэл N/X нь N\sqrt N -с бага байна. Гэхвдээ бид тухайн завсарт шалгасан тул боломжгүй. Үүнээс бид тухайн тоог анхны тоо эсэхийг N \sqrt N -р шалгаж чадахнээ.

Ахны тоонуудыг байгуулах

1-с N хүртэлх бүх анхны тоог байгуулцгаая. Үүнийг ойролцоогоор N∗(N) N*\sqrt (N) үйлдлээр хийж чадна. Гэхдээ мэдээж үүнээс хурднаар хэрхэн хийх вэ?

Бидэнд тухайн тоо анхны тоо эсэхийг тэмдэглэх Prime гэсэн жагсаалт байгаа гэж үзье. Тэгвэл Prime[1] = false, Prime[2] true байна. 2-г хамгийн эхний анхны тоо гэдгийг мэднэ. Тэгвэл 2-д хуваагддаг N хүртэлх бүх тоонууд анхны тоо болж чадахгүй тиймээс энэхүү тоонуудыг анхны тоо биш гэж тэмдэглэе. Дараагийн тоо нь 3 ба энэ нь өмнөх бүх анхны тоондоо хуваагдаагүй тул энэ тоо нь анхны тоо. Тэгвэл 3-д хуваагддаг дараагийн бүх тоонууд анхны тоо биш. Дараагийн тоо нь 4 ба энэ нь 2-д хуваагддаг тул анхны тоо биш гэж тэмдэглэгдсэн. Дараагийн тоо нь 5 ба энэ нь анхы тоо биш гэж тэмдэглэгдээгүй ба өмнөх бүх анхны тоондоо хуваагдаагүй тул анхны тоо. Тэгвэл 5-д хуваагддаг дараачийн тоонууд нь анхны тоо биш болох юм.

Image

Энэ мэтчилэн бодвол хугацааны үнэлгээ нь ∑p≤NN/p≈nln⁡ln⁡n \begin{aligned} \sum\nolimits_{p\leq N} N/p \approx n \ln \ln n \end{aligned}

байдаг бөгөөд үүнийг Sieve of Eratosthenes гэж нэрлэдэг. Доор кодыг оруулав

#include <bits/stdc++.h>  
using namespace std;  
      
    int n;  
    bool Prime[2000000]; // Prime[i] нь i гэсэн тоо анхны тоо бол 0 үгүй бол 1  
  
int main() {  
    cin >> n;  
    Prime[1] = 1;  
  
    for(int i = 2; i*i <= n; i++) {  
        if(Prime[i]) continue; // i тоо нь анхны тоо биш тул алгасна.  
          
        // i-д хуваагддаг дараачийн бүх тоонууд нь анхны тоо биш тул тэмдэглэнэ.  
        for(int j = i+i; j <= n; j += i) {  
            Prime[j] = 1;  
        }  
    }  
    
    for(int i = 1; i <= n; i++) {
    	if(!Prime[i]) {	// анхны тоо
    		cout << i << " ";
    	}
    }
    cout << endl;  
    return 0;  
}