Cara menggunakan algoritma penghakiman nombor perdana dalam C++

Cara menggunakan algoritma penghakiman nombor perdana dalam C++

Pertimbangan nombor perdana ialah masalah biasa dalam algoritma, yang memerlukan penilaian sama ada sesuatu yang diberikan nombor ialah nombor perdana (nombor perdana). Dalam C++, kita boleh menggunakan algoritma yang berbeza untuk menyelesaikan masalah ini. Artikel ini akan memperkenalkan dua algoritma penghakiman nombor perdana biasa dan memberikan contoh kod yang sepadan.

1. Kaedah brute force (kaedah kekerasan)
   Kaedah brute force (kaedah kekerasan) ialah algoritma yang paling langsung Ideanya adalah untuk membandingkan nombor yang diberikan dengan nilai yang lebih kecil daripada Semua nombor nombor tertakluk kepada operasi selebihnya Jika terdapat nombor yang boleh membahagikan nombor itu, maka nombor itu bukan nombor perdana, jika tidak ia adalah nombor perdana.

Berikut ialah contoh kod C++ yang menggunakan kaedah brute force untuk menentukan sama ada nombor yang diberikan adalah perdana:

#include <iostream>

bool isPrime(int n)
{
    if (n < 2)   // 小于2的数都不是素数
        return false;
        
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    
    return true;
}

int main()
{
    int num;
    std::cout << "请输入一个整数：";
    std::cin >> num;
    
    if (isPrime(num))
        std::cout << num << " 是素数。" << std::endl;
    else
        std::cout << num << " 不是素数。" << std::endl;
        
    return 0;
}

2. Ayak Eratosthenes Kaedah
   Kaedah Ayak Eratosthenes ialah algoritma penghakiman nombor perdana berdasarkan kaedah ayak. Ideanya adalah untuk menjana jadual semua nombor dahulu bermula dari 2 hingga julat tertentu, dan kemudian menapis nombor bukan perdana. satu demi satu nombor, dan yang tinggal pada akhirnya adalah nombor perdana.

Berikut ialah contoh kod C++ yang menggunakan penapis Eratosthenes untuk menentukan sama ada nombor yang diberikan adalah perdana:

#include <iostream>
#include <vector>

bool isPrime(int n)
{
    if (n < 2)   // 小于2的数都不是素数
        return false;
        
    std::vector<bool> is_prime(n + 1, true);
    is_prime[0] = is_prime[1] = false;
    
    for (int i = 2; i * i <= n; i++)
    {
        if (is_prime[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                is_prime[j] = false;
            }
        }
    }
    
    return is_prime[n];
}

int main()
{
    int num;
    std::cout << "请输入一个整数：";
    std::cin >> num;
    
    if (isPrime(num))
        std::cout << num << " 是素数。" << std::endl;
    else
        std::cout << num << " 不是素数。" << std::endl;
        
    return 0;
}

Di atas adalah dua nombor biasa C++ contoh kod algoritma penentuan nombor perdana Dengan menjalankan kod ini, kita boleh menentukan sama ada nombor yang diberikan ialah nombor perdana. Sudah tentu, kedua-dua algoritma mempunyai kelebihan dan kekurangan mereka sendiri Dalam senario aplikasi tertentu, algoritma yang sesuai perlu dipilih berdasarkan situasi sebenar. Saya harap artikel ini akan membantu pembaca memahami dan menggunakan algoritma penghakiman nombor perdana dalam C++.

Atas ialah kandungan terperinci Cara menggunakan algoritma penghakiman nombor perdana dalam C++. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!