Kiểm tra xem một số có phải là Nguyên tố Nguyên tố hay không trong C ++

Khái niệm

Đối với số dương n đã cho, nhiệm vụ là xác minh xem n có phải là số nguyên tố sơ cấp hay không. Chúng ta phải in ‘CÓ’ nếu n là số nguyên tố nguyên tố, nếu không thì in ‘KHÔNG.

Số nguyên tố Nguyên tố - Đối với Toán học, một số nguyên tố Nguyên tố được định nghĩa là một số nguyên tố có dạng pN # + 1 hoặc pN # - 1, trong đó pN # là số nguyên tố của pN sao cho tích của N số nguyên tố đầu tiên.

Đầu vào - n =7

Đầu ra - CÓ

7 là số nguyên tố Nguyên tố có dạng pN + 1 với N =2, Nguyên tố là 2 * 3 =6 và 6 + 1 =7.

Đầu vào - n =29

Đầu ra - CÓ

29 là số nguyên tố Nguyên tố có dạng pN - 1 với N =3, Nguyên tố là 2 * 3 * 5 =30 và 30-1 =29.

Sau đây, một số số nguyên tố Nguyên tố đầu tiên được hiển thị - 2, 3, 5, 7, 29, 31, 211, 2309, 2311, 30029

Phương pháp tiếp cận

• Chúng ta phải tạo tất cả các số nguyên tố trong phạm vi bằng cách áp dụng Sieve of Eratosthenes.

• Xác minh xem N có phải là số nguyên tố hay không, Nếu N không phải là số nguyên tố thì in Không

• Nếu không, bắt đầu từ số nguyên tố đầu tiên (tức là 2) bắt đầu nhân số nguyên tố tiếp theo và tiếp tục xác minh xem sản phẩm + 1 =N hay sản phẩm - 1 =N hay không

• Người ta đã thấy rằng nếu sản phẩm + 1 =N hoặc sản phẩm-1 =N, thì N là Nguyên tố sơ cấp, ngược lại thì không.

Ví dụ

// 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;
}

Đầu ra

YES