So verwenden Sie den Algorithmus zur Primzahlbeurteilung in C++

So verwenden Sie den Algorithmus zur Primzahlbeurteilung in C++

Die Primzahlbeurteilung ist ein häufiges Problem bei Algorithmen. Sie erfordert die Beurteilung, ob eine bestimmte Zahl eine Primzahl (Primzahl) ist. In C++ können wir verschiedene Algorithmen verwenden, um dieses Problem zu lösen. In diesem Artikel werden zwei gängige Algorithmen zur Primzahlbeurteilung vorgestellt und entsprechende Codebeispiele gegeben.

1. Brute-Force-Methode (Brute-Force-Methode) ist der direkteste Algorithmus. Seine Idee besteht darin, eine Restoperation für eine bestimmte Zahl und alle Zahlen durchzuführen, die kleiner als die Zahl sind Wenn eine Zahl durch die Zahl teilbar ist, dann ist die Zahl keine Primzahl, andernfalls ist sie eine Primzahl.
   

Das Folgende ist ein C++-Codebeispiel, das die Brute-Force-Methode verwendet, um zu bestimmen, ob eine bestimmte Zahl eine Primzahl ist:

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

Die Sieve of Eratosthenes-Methode
2. Die Sieve of Eratosthenes-Methode ist eine Primzahl, die auf der Sieve-Methode The basiert Die Idee des Beurteilungsalgorithmus besteht darin, zunächst eine Tabelle aller Zahlen beginnend bei 2 bis zu einem bestimmten Bereich zu erstellen und dann die Nicht-Primzahlen nacheinander zu filtern. Am Ende bleibt die Primzahl übrig.
   

Das Folgende ist ein C++-Codebeispiel, das das Sieb von Eratosthenes verwendet, um zu bestimmen, ob eine bestimmte Zahl eine Primzahl ist:

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

Die oben genannten sind C++-Codebeispiele für zwei gängige Algorithmen zur Primzahlbestimmung kann bestimmen, ob eine gegebene Zahl eine Primzahl ist. Natürlich haben beide Algorithmen ihre eigenen Vor- und Nachteile. In bestimmten Anwendungsszenarien muss der geeignete Algorithmus basierend auf der tatsächlichen Situation ausgewählt werden. Ich hoffe, dass dieser Artikel den Lesern hilft, den Algorithmus zur Primzahlbeurteilung in C++ zu verstehen und zu verwenden.

Das obige ist der detaillierte Inhalt vonSo verwenden Sie den Algorithmus zur Primzahlbeurteilung in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!