ในปัญหานี้ เราได้รับตัวเลข N และหน้าที่ของเราคือตรวจสอบว่าเป็นจำนวนเฉพาะหรือไม่
การทดสอบเบื้องต้น เป็นอัลกอริธึมที่ใช้ในการตรวจสอบว่าจำนวนที่กำหนดเป็นจำนวนเฉพาะหรือไม่
จำนวนเฉพาะเป็นตัวเลขที่สามารถหารด้วยตัวเองเท่านั้น ตัวอย่าง :2, 3, 5, 7
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหาของเรากัน
Input: 11 Output: Yes
มีหลายวิธีในการตรวจสอบการทดสอบเบื้องต้นของตัวเลข
วิธีง่ายๆ วิธีหนึ่งในการตรวจสอบความเป็นเอกเทศคือการตรวจสอบการหารของตัวเลขด้วยจำนวนทั้งหมดที่น้อยกว่า N หากจำนวนใดหาร N แสดงว่าไม่ใช่จำนวนเฉพาะ
ตรวจสอบทั้งหมด i =2 - n-1 ถ้า n/i ==0 นั่นไม่ใช่จำนวนเฉพาะ
วิธีนี้ทำให้มีประสิทธิภาพมากขึ้นโดยการเปลี่ยนแปลงเล็กน้อยในอัลกอริทึม
อันดับแรก เราควรตรวจสอบค่าจนถึง √n แทนที่จะเป็น n วิธีนี้จะช่วยประหยัดค่าลูปได้มาก √n รวมค่าของปัจจัยที่น่าจะเป็นทั้งหมดของ n.
การเปลี่ยนแปลงอื่นๆ อาจตรวจสอบการหารด้วย 2 และ 3 จากนั้นตรวจสอบค่าลูปจาก 5 เป็น √n
โปรแกรมแสดงการใช้งานอัลกอริธึมนี้
ตัวอย่าง
#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.
วิธีอื่นที่มีประสิทธิภาพมากกว่าในการตรวจสอบจากความเป็นอันดับหนึ่งของตัวเลขคือการใช้วิธีของ Fermat ซึ่งอิงตามทฤษฎีบทเล็กๆ ของแฟร์มาต์
ทฤษฎีบทเล็กๆ ของแฟร์มาต์ สำหรับจำนวนเฉพาะ N ทุกค่าของ x ที่เป็นของ (1, n-1) ด้านล่างนี้เป็นความจริง
a n-1 ≡ 1 (mod n) or a n-1 % n = 1
โปรแกรมแสดงการนำทฤษฎีบทนี้ไปปฏิบัติ
ตัวอย่าง
#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
