Sàng nguyên tố trong thời gian tuyến tính

SÀNG NGUYÊN TỐ TUYẾN TÍNH

Cấu trúc dữ liệu int uocso[...]
Lúc đầu cho uocso[i] = 0 với uy ước uocso[i] = 0 thì i là số nguyên tố.
Sau đó:
- Nếu uocso[i] = 0 tức là i là số nguyên tố ta gán uocso[i] = i, nghĩa là i là số nguyên tố nên ước số của i là số i
- Nếu uocso[i] = k thì ước số nguyên tố nhỏ nhất của i là k

Nhận xét: sau khi chạy xong thuật toán thì có thể dùng mảng uocso[] theo 2 cách:
Cách 1: Dùng để kiểm tra số nguyên i có là số nguyên tố không: nếu uocso[i]=i thì i là số nguyên tố
Cách 2: Dùng để biết số nguyên tố nhỏ nhất của hợp số i là bao nhiêu, từ đó dùng để phân tích nhanh số nguyên i ra thành các thừa số nguyên tố

Cấu trúc dữ liệu vector<int> primes
primes dùng để chứa các số nguyên tố

Thuật toán: 
Xét từng số i từ 2 đến N
  - Nếu i là số nguyên tố thì: thêm i vào primes và cho uocso[i]=i
  - Xét các số nguyên tố đã lưu trong mảng primes và số nguyên tố này nhỏ hơn hay bằng ước số nguyên tổ nhỏ nhất của số i (tức là số nguyên tố lưu trong uocso[i]):
     + Bỏ đi các bội i là i*primes[j] hay ghi nhận uocso[i*primes[j]] là primes[j]



Chương trình:
const int N = 32000000
vector<int> primes;
int uocso[N];

void Sang() {
  for (int i=2; i<=N; i++) {
    if (uocso[i] == 0) {
      uocso[i] = i;
      primes.push_back(i);
    }

    for (int j=0; j<primes.size() && 
                  primes[j]<=uocso[i] && 
                  i*primes[j]<=N; j++)
      uocso[i*primes[j]] = primes[j];
  }
}

Sàng nguyên tố trên đoạn [L, R]

SÀNG NGUYÊN TỐ TRÊN ĐOẠN [L, R]

Bài toán: Hãy tìm các số nguyên thuộc đoạn [L, R], trong đó (1<=L<=R<=2.000.000.000 và R-L<=1.000.000).

Thuật toán:
- Trường hợp 1. Nếu R<=1.000.000 thì áp dụng phương pháp sàng bình thường
- Trường hợp 2. Nếu R>1.000.000 thì ta có có nhận xét

Nhận xét: nếu số nguyên n không là số nguyên tố thì n có ước số là sqrt(n).
Trong trường hợp n là số lớn nhất như trong đề bài, tức là n=2.000.000.000 thì n có ước số nhỏ hơn hay bằng sqrt(n)=44.722. Vậy ta sẽ tìm các số nguyên tố nhỏ hơn hay bằng 44.722


Bước 1. Sàng các số nguyên tố trên đoạn [1...44.722], để cho gọn gàng ta có thể sàng trên đoạn [1...50.000], còn nếu chính xác thì ta chỉ cần sàng trên đoạn [1...sqrt(R)]
Bước 2. Xét các số nguyên tố i trong đoạn [1...sqrt(R)], ta sẽ loại bỏ đi các số không nguyên tố j là bội của i. Nhưng để cho nhanh ta phải tính toán sao cho j thuộc [L, R]

Cách tính j:
- Nếu L chia hết cho i thì j=L
- Nếu L không chia hết cho i thì:
  + Tìm số lớn nhất gần L mà chia hết cho i, tức là ta lấy số L trừ đi phần dư khi chia L cho i: k=L-(L%i). Lúc này k chia hết cho i.
  + Vậy j = k+i sẽ là số lớn hơn L và chia hết cho i

Cách đánh dấu đoạn [L, R]:
- Vì L, R có thể lên đến 2 tỷ, nhưng đoạn từ L đến R chỉ có tối đa 1 triệu số nên ta ánh xạ đoan [L, R] sang đoạn [0, R-L]

#include <bits/stdc++.h>
using namespace std;

bitset<1000000+10> isSmallPrime;
bitset<1000000+10> isLargePrime;

vector<int> primes;

void SangTrenDoan(int L, int R) {
  // Buoc 1: Sang các số nguyên tố <= sqrt(R)
  int n = (int) sqrt(R);
  isSmallPrime.set(); isSmallPrime[0]=isSmallPrime[1]=false;
  for (int i=4; i<=n; i+=2) isSmallPrime[i]=false;

  for (int i=3; i*i<=n; i+=2)
    if (isSmallPrime[i])
      for (int j=i*i; j<=n; j+=i) isSmallPrime[j]=false;

  // Bước 2: Sang các số nguyên tố thuộc đoạn [L, R]
  isLargePrime.set();
  for (int i=2; i*i<=R; i++)
    if (isSmallPrime[i]) {
      if (L%i==0) 
        for (int j=L; j<=R; j+=i) isLargePrime[j-L]=false;
      else if (L>i) {
        int du = L%i;
        for (int j=(L-du)+i; j<=R; j+=i) isLargePrime[j-L]=false;
      }
    }
   
  for (int i=L; i<=R; i++)
    if (isLargePrime[i-L]) primes.push_back(i);
}

Ước số chung lớn nhất - Bội số chung nhỏ nhất

Thuật toán tìm ước số chung lớn nhất - bội số chung nhỏ nhất

Khái niệm: Ước số chung lớn nhất của hai số nguyên a và b, ký hiêu là USCLN(a, b), là số nguyên d lớn nhất mà cả a và b đều chia hết cho d.

Công thức: USCLN(a, b) = USCLN(b, a mod b)

Nhận xét: Công thức đệ quy trên sẽ dừng khi b=0 và kết quả là a

Chương trình:

#include <bits/stdc++.h>

using namespace std;

int USCLN(int a, int b) {

  if (b==0) return a;

  return USCLN(b, a%b);

}

Khái niệm: Bội số chung nhỏ nhất của hai số nguyên a và b, ký hiêu là BSCNN(a, b), là số nguyên d nhỏ nhất mà d đều chia hết cho cả a và b.

Công thức: BSCNN(a, b) = (a*b)/USCLN(a, b)

Nhận xét: Cả a và b đều chia hết cho USCLN(a, b) nên chúng ta có thể viết lại công thức trên để tránh việc tràn số khi tính toán phép nhân trước: BSCNN(a, b) = a/USCLN(a, b)*b;

Chương trình:

#include <bits/stdc++.h>

using namespace std;

int BSCNN(int a, int b) {

  return a/USCLN(a, b)/b;

}

Phân tích thừa số nguyên tố

Thuật toán phân tích thừa số nguyên tố

Chức năng: Phân tích số nguyên n thành các thừa số nguyên tố

Chương trình:

#include <bits/stdc++.h>

using namespace std;

vector<int> p, alpha;

void Factor(int n) {

  if ((n<=1000000 && isPrime[n]) || (n>1000000 && IsPrime(n) == true)) {

    p.push_back(n); alpha.push_back(1);

    return;

  }

  int i=0;

  while (n>1) {

    while ((i<primes.size()) && (n%primes[i]!=0)) i++;

    if (i==primes.size()-1) {

      p.push_back(n); alpha.push_back(1);

      return;

    }

    int count=0;

    while (n%primes[i] == 0) {

      count++; 

      n = n/primes[i];

    }

    p.push_back(primes[i]); alpha.push_back(count);

    if ((n<=1000000 && isPrime[n])) {

      p.push_back(n); alpha.push_back(1);

      return;

    }

  }

}

Kiểm tra số nguyên tố

Thuật toán kiểm tra số nguyên tố

Chức năng: Kiểm tra số nguyên n có phải là số nguyên tố không

Thuật toán 1: Kiểm tra số n có chia hết cho các số i, số nguyên i chạy từ 2 đến sqrt(n), hay không
Thuật toán 2: Cải tiến giá trị của biến chạy i
Số nguyên i luôn có một trong các dạng sau:
  (1) 6k+1, 6k-1
  (2) 6k+2, 6k-2

  (3) 6k+3, 6k-3

Trường hợp i có dạng 6k+2, 6k-2, lúc đó i chia hết cho 2. Nếu n chia hết cho i thì n chia hết cho 2
Trường hợp i có dạng 6k+3, 6k-3, lúc đó i chia hết cho 3. Nếu n chia hết cho i thì n chia hết cho 3

Chúng ta kiểm tra trường hợp i có dạng (1) và (2) riêng bằng cách kiểm tra n có chia hết cho 2 hay 3 không

Sau đó chúng ta xét i có dạng (3), tức là i có giá trị: (5, 7), (11, 13), (17, 19), ...

Độ phức tạp: O(sqrt(n))

Chương trình:

#include <bits/stdc++.h>

using namespace std;

bool IsPrime(int n) {

  if (n<2) return false;

  if (n==2 || n==3) return true;

  if (n%2==0 || n%3==0) return false;

  for (int i=5; i*i<=n; i+=6)

    if (n%i==0 || n%(i+2)==0) return false;

  return false;

}

Nếu chúng ta đã tính sàng nguyên tố hoặc việc tính sàng nguyên tố không ảnh hưởng độ phức tạp của thuật toán cả chương trình thì chúng ta có thuật toán kiểm tra số nguyên tố sau hiệu quả hơn bằng cách xét xem n có chia hết các số nguyên tố không.

#include <bits/stdc++.h>

using namespace std;

bool IsPrime(int n) {

  if (n<2) return false;

  if (n<=1000000) return isPrime[i];

  for (int i=0; primes[i]*primes[i]<=n; i++)

    if (n%primes[i]==0) return false;

  return false;

}

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);

}