Primality Test ใน C++

ในปัญหานี้ เราได้รับตัวเลข N และงานของเราคือตรวจสอบว่ามันเป็นจำนวนเฉพาะหรือไม่

Primality test คืออัลกอริทึมที่ใช้ตรวจสอบว่าตัวเลขที่กำหนดเป็นเฉพาะหรือไม่

Prime number คือตัวเลขที่หารด้วยตัวมันเองได้อย่างเดียว ตัวอย่าง: 2, 3, 5, 7

ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหาของเรา:

Input: 11 Output: Yes

มีหลายวิธีในการตรวจสอบ primality test ของตัวเลข

วิธีง่ายหนึ่งในการตรวจสอบ primality คือการตรวจสอบการหารของตัวเลขด้วยตัวเลขทั้งหมดน้อยกว่า N ถ้าตัวเลขไหนหาร N ลงตัว แล้วมันไม่ใช่จำนวนเฉพาะ

ตรวจสอบสำหรับ i = 2 - n-1 ทั้งหมด ถ้า n/i == 0 มันไม่ใช่ prime number

วิธีนี้สามารถทำให้มีประสิทธิภาพมากขึ้นโดยการเปลี่ยนแปลงเล็กน้อยในอัลกอริทึม

ก่อนอื่น เราควรตรวจสอบค่าจนถึง √n แทน n นี่จะประหยัดค่าลูปมาก √n รวมค่าของปัจจัยที่เป็นไปได้ทั้งหมดของ n

การเปลี่ยนแปลงอื่นอาจเป็นการตรวจสอบการหารด้วย 2 และ 3 แล้วตรวจสอบค่าลูปจาก 5 ถึง √n

โปรแกรมแสดงการนำอัลกอริทึมนี้ไปใช้

ตัวอย่างโค้ด (วิธี Basic)

#include <iostream>
using namespace std;

bool isPrimeNumber(int n){
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

int main() {
    int n = 341;
    if (isPrimeNumber(n))
        cout<<n<<" is prime Number.";
    else
        cout<<n<<" is not prime Number.";
    return 0;
}

ผลลัพธ์

341 is not prime Number.

วิธีที่มีประสิทธิภาพมากกว่าในการตรวจสอบ primality ของตัวเลขคือการใช้ Fermat's method ซึ่งอิงตาม Fermat's Little Theorem

Fermat's Little Theorem สำหรับ prime number N ทุกค่าของ x ที่อยู่ใน (1, n-1) ข้อความด้านล่างเป็นจริง:

a^(n-1) ≡ 1 (mod n) หรือ a^(n-1) % n = 1

โปรแกรมแสดงการนำทฤษฎีนี้ไปใช้:

ตัวอย่างโค้ด (Fermat's Method)

#include <iostream>
#include <math.h>
using namespace std;

int power(int a, unsigned int n, int p) {
    int res = 1;
    a = a % p;
    while (n > 0){
        if (n & 1)
            res = (res*a) % p;
        n = n/2;
        a = (a*a) % p;
    }
    return res;
}

int gcd(int a, int b) {
    if(a < b)
        return gcd(b, a);
    else if(a%b == 0)
        return b;
    else return gcd(b, a%b);
}

bool isPrime(unsigned int n, int k) {
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;
    while (k>0){
        int a = 2 + rand()%(n-4);
        if (gcd(n, a) != 1)
            return false;
        if (power(a, n-1, n) != 1)
            return false;
        k--;
    }
    return true;
}

int main() {
    int k = 3, n = 23;
    if(isPrime(n, k)){
        cout<<n<<" is a prime number";
    }
    else
        cout<<n<<" is not a prime number";
    return 0;
}

ผลลัพธ์

23 is a prime number