Sieve of Eratosthenes
тухай.
N тоог анхны тоо эсэхийг sqrt(N) үйлдлээр шалгаж болно. Тэгвэл 1-с N хүртэлх бүх анхны тоог ол гэсэн бол үүнийг ашиглавал ойролцоогоор N*sqrt(N) үйлдлээр хийх юм. Одоо бичих алгоритм нь илүү хурдан юм. Анхны тоо гэдэг нь зөвхөн 2 ширхэг натурал тоон хуваагчтай тоо ба өөрөөр хэлбэр анхны тоо нь өмнөх ямар ч анхны тоондоо хуваагддаггүй гэсэн үг. 2-г хамгийн эхний анхны тоо гэдгийг мэднэ. Тэгвэл 2-д хуваагддаг дараагийн бүх тоонууд анхны тоо болж чадахгүй. Тэгвэл энэхүү тоонуудыг анхны тоо биш гэж тэмдэглэе. Дараагийн тоо нь 3 ба энэ нь өмнөх бүх анхны тоондоо хуваагдаагүй тул энэ тоо нь анхны тоо. Тэгвэл 3-д хуваагддаг дараагийн бүх тоонууд анхны тоо биш. Дараагийн тоо нь 4 ба энэ нь 2-д хуваагддаг тул анхны тоо биш гэж тэмдэглэгдсэн. Дараагийн тоо нь 5 ба энэ нь анхы тоо биш гэж тэмдэглэгдээгүй ба өмнөх бүх анхны тоондоо хуваагдаагүй тул анхны тоо. Тэгвэл 5-д хуваагддаг дараачийн тоонууд нь анхны тоо биш болох юм. Энэ мэтчилэн бодвол хугацааны үнэлгээ нь N/p[1] + N/p[2] + N/p[3] + ... + N/p[k] болох ба энд p[i] нь i-р анхны тоо юм. Тиймээс энэхүү алгоритмыг ашиглан N хүртэлх анхны тоог маш хурдан олж болно. Доорх код энэ хаягт байгаа.
- //sieve-н алгоритм
- #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;
- }
Comments
Post a Comment