Thứ Hai, 22 tháng 10, 2018

Sàng nguyên tố Eratosthenes

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