Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ प्रोग्राम बेली-पीएसडब्ल्यू प्राइमैलिटी टेस्ट करने के लिए


बेली-पीएसडब्ल्यू प्राइमैलिटी टेस्ट, यह टेस्ट रॉबर्ट बेली, कार्ल पोमेरेंस, जॉन सेल्फ्रिज, और सैमुअल वैगस्टाफ के नाम पर रखा गया है। यह एक टेस्ट है जो जांचता है कि कोई संख्या कम्पोजिट नंबर है या संभावित रूप से प्राइम।

एल्गोरिदम

मिलरटेस्ट()

Begin
    बूलियन टाइप का फंक्शन MillerTest घोषित करें।
    MT_dt और MT_num को इंटीजर डेटाटाइप का घोषित करें और पैरामीटर के रूप में पास करें।
    MT_a और MT_x को इंटीजर डेटाटाइप का घोषित करें।
    MT_a = 2 + rand() % (MT_num - 4) इनिशियलाइज़ करें।
    MT_x = pow(MT_a, MT_dt, MT_num) इनिशियलाइज़ करें।
    if (MT_x == 1 || MT_x == MT_num - 1) तो
        return true.
    while (MT_dt != MT_num - 1) do
        MT_x = (MT_x * MT_x) % MT_num.
        MT_dt *= 2.
        if (MT_x == 1) तो return false.
        if (MT_x == MT_num - 1) तो return true.
    return false.
End.

C++ कार्यान्वयन

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

int pow(int base, unsigned int exp, int mod) {
    int result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp & 1)
            result = (result * base) % mod;
        exp = exp >> 1;
        base = (base * base) % mod;
    }
    return result;
}

bool MillerTest(int d, int n) {
    int a = 2 + rand() % (n - 4);
    int x = pow(a, d, n);
    if (x == 1 || x == n - 1)
        return true;
    while (d != n - 1) {
        x = (x * x) % n;
        d *= 2;
        if (x == 1) return false;
        if (x == n - 1) return true;
    }
    return false;
}

bool isPrime(int n, int k) {
    if (n <= 1 || n == 4) return false;
    if (n <= 3) return true;
    
    int d = n - 1;
    while (d % 2 == 0) d /= 2;
    
    for (int i = 0; i < k; i++)
        if (MillerTest(d, n) == false)
            return false;
    return true;
}

int main() {
    int iter = 50;
    long num1, num2;
    cout << "Enter the first number: ";
    cin >> num1;
    if (isPrime(num1, iter))
        cout << num1 << " is a prime number\n";
    else
        cout << num1 << " is a composite number\n";
    
    cout << "Enter another number: ";
    cin >> num2;
    if (isPrime(num2, iter))
        cout << num2 << " is a prime number\n";
    else
        cout << num2 << " is a composite number\n";
    return 0;
}

आउटपुट

Enter the first number: 23
23 is a prime number

Enter another number: 45
45 is a composite number

नोट

यह कार्यान्वयन मिलर-रैबिन टेस्ट दिखाता है जो बेली-पीएसडब्ल्यू का एक भाग है। पूर्ण बेली-पीएसडब्ल्यू टेस्ट में लुकास टेस्ट भी शामिल होता है। यह कोड शैक्षिक उद्देश्यों के लिए सरलीकृत संस्करण है।

  1. - C++ प्रोग्राम: किसी भी मैट्रिक्स का LU अपघटन

    LU अपघटन क्या है? LU अपघटन एक मैट्रिक्स को निचले त्रिकोणीय मैट्रिक्स (L) और ऊपरी त्रिकोणीय मैट्रिक्स (U) के गुणनफल के रूप में व्यक्त करता है। LU का अर्थ है Lower-Upper। उदाहरण दिया गया मैट्रिक्स: 1 1 0 2 1 3 3 1 1 L मैट्रिक्स: 1 0 0 2 -1 0 3 -2 -5 U मैट्रिक्स: 1 1 0 0 1 -3 0 0 1 C++ प्रोग्राम उ

  1. - C++ प्रोग्राम: सम्मिश्र संख्या गुणन

    सम्मिश्र संख्याएं सम्मिश्र संख्याएं a+bi के रूप में व्यक्त की जाती हैं, जहां i काल्पनिक इकाई है (i² = -1) और a, b वास्तविक संख्याएं हैं। उदाहरण 2+3i, 5+9i, 4+2i गुणन सूत्र (a+bi) × (c+di) = (ac - bd) + (ad + bc)i C++ प्रोग्राम उदाहरण #include <iostream> using namespace std; int main() {

  1. - C++ में मैट्रिक्स गुणा करने का प्रोग्राम

    मैट्रिक्स संख्याओं का एक आयताकार सरणी है जो पंक्तियों और कॉलम के रूप में व्यवस्थित होता है। मैट्रिक्स का एक उदाहरण निम्नलिखित है। एक 3*2 मैट्रिक्स में 3 पंक्तियाँ और 2 कॉलम होते हैं जैसा कि नीचे दिखाया गया है: 8 1 4 9 5 6 मैट्रिक्स गुणा करने का एक प्रोग्राम निम्नलिखित है। उदाहरण #include<iostream