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;

}