แนวคิด
สำหรับจำนวนบวกที่กำหนด n ภารกิจคือตรวจสอบว่า n เป็นจำนวนเฉพาะดั้งเดิมหรือไม่ เราต้องพิมพ์ 'YES' ถ้า n เป็นจำนวนเฉพาะดั้งเดิม ไม่เช่นนั้นให้พิมพ์ 'NO'
Primorial Prime - ในแง่ของคณิตศาสตร์ Primorial Prime ถูกกำหนดให้เป็นจำนวนเฉพาะของรูปแบบ pN# + 1 หรือ pN# – 1 โดยที่ pN# เป็นจำนวนเฉพาะของ pN ซึ่งเป็นผลมาจากผลลัพธ์ของจำนวนเฉพาะ N ตัวแรก
ป้อนข้อมูล − n =7
ผลผลิต - ใช่
7 คือไพรมอเรียลไพรม์ของรูปแบบ pN + 1 สำหรับ N=2 ไพรมอเรียลคือ 2*3 =6 และ 6+1 =7
ป้อนข้อมูล − n =29
ผลผลิต - ใช่
29 คือไพรมอเรียลไพรม์ของรูปแบบ pN - 1 สำหรับ N=3 ไพรมอเรียลคือ 2*3*5 =30 และ 30-1 =29
ต่อไปนี้ แสดงไพรมอเรียลสองสามตัวแรก − 2, 3, 5, 7, 29, 31, 211, 2309, 2311, 30029
แนวทาง
-
เราต้องสร้างจำนวนเฉพาะทั้งหมดในช่วงโดยใช้ตะแกรงของ Eratosthenes
-
ตรวจสอบว่า N เป็นจำนวนเฉพาะหรือไม่ ถ้า N ไม่ใช่จำนวนเฉพาะ ให้พิมพ์ No
-
มิฉะนั้น ให้เริ่มจากจำนวนเฉพาะแรก (เช่น 2 ) ให้เริ่มคูณจำนวนเฉพาะถัดไปและตรวจดูว่าผลิตภัณฑ์ + 1 =N หรือผลิตภัณฑ์ – 1 =N หรือไม่
-
จะเห็นได้ว่าหาก product+1=N หรือ product-1=N แล้ว N จะเป็น Primorial Prime ไม่เช่นนั้นจะไม่ใช่
ตัวอย่าง
// CPP program to check Primorial Prime
#include <bits/stdc++.h>
using namespace std;
#define MAX 10000
vector<int> arr1;
bool prime1[MAX];
void SieveOfEratosthenes1(){
memset(prime1, true, sizeof(prime1));
for (int p = 2; p * p < MAX; p++) {
if (prime1[p] == true) {
for (int i = p * 2; i < MAX; i += p)
prime1[i] = false;
}
}
for (int p = 2; p < MAX; p++)
if (prime1[p])
arr1.push_back(p);
}
bool isPrimorialPrime1(long n){
// If n is not prime Number
// return flase
if (!prime1[n])
return false;
long long product1 = 1;
int i = 0;
while (product1 < n) {
product1 = product1 * arr1[i];
if (product1 + 1 == n || product1 - 1 == n)
return true;
i++;
}
return false;
}
// Driver code
int main(){
SieveOfEratosthenes1();
long n = 29;
// Check if n is Primorial Prime
if (isPrimorialPrime1(n))
cout << "YES\n";
else
cout << "NO\n";
return 0;
} ผลลัพธ์
YES
