Thuật toán Sàng nguyên tố Eratosthenes
Chức năng: Sàng nguyên tố Eratosthenes có hai chức năng
(1) Liệt kê các số nguyên tố nhỏ hơn hay bằng n
(2) Tạo mảng dùng để truy vấn kiểm tra môt số có phải là số nguyên tố hay không
Độ phức tạp: O(N*loglogN)
Chương trình:
#include <bits/stdc++.h>
using namespace std;
bitset<1000000+10> isPrime;
vector<int> primes;
void Eratosthenes(int n) {
isPrime.set(); isPrime[0]=isPrime[1]=false;
for (int i=4; i<=n; i+=2) isPrime[i]=false;
for (int i=2; i*i<=n; i++)
if (isPrime[i])
for (int j=i*i; j<=n; j+=i) isPrime[j] = false;
for (int i = 2; i <= n; i++) if (isPrime[i]) primes.push_back(i);
}
Không có nhận xét nào:
Đăng nhận xét