Comment utiliser l'algorithme de jugement des nombres premiers en C++

Comment utiliser l'algorithme de jugement des nombres premiers en C++

Le jugement des nombres premiers est un problème courant dans les algorithmes. Il nécessite de juger si un nombre donné est un nombre premier (nombre premier). En C++, nous pouvons utiliser différents algorithmes pour résoudre ce problème. Cet article présentera deux algorithmes courants de jugement de nombres premiers et donnera des exemples de code correspondants.

1. Méthode de force brute (méthode de force brute)
   La méthode de force brute (méthode de force brute) est l'algorithme le plus direct. Son idée est d'effectuer une opération de reste sur un nombre donné et tous les nombres inférieurs au nombre. Si un nombre est divisible par le nombre, alors ce nombre n'est pas un nombre premier, sinon c'est un nombre premier.

Ce qui suit est un exemple de code C++ qui utilise la méthode de la force brute pour déterminer si un nombre donné est premier :

#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. La méthode Sieve d'Eratosthène
   La méthode Sieve d'Eratosthène est un nombre premier basé sur la méthode du tamis. L'idée de l'algorithme de jugement est de générer d'abord un tableau de tous les nombres allant de 2 à une plage donnée, puis de filtrer les nombres non premiers un par un, et ce qui reste à la fin est le nombre premier.

Ce qui suit est un exemple de code C++ qui utilise le tamis d'Eratosthène pour déterminer si un nombre donné est un nombre premier :

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

Ce qui précède sont des exemples de code C++ de deux algorithmes courants de détermination de nombres premiers. En exécutant ces codes, nous avons. peut déterminer si un nombre donné est premier. Bien entendu, les deux algorithmes ont leurs propres avantages et inconvénients. Dans des scénarios d’application spécifiques, l’algorithme approprié doit être sélectionné en fonction de la situation réelle. J'espère que cet article aidera les lecteurs à comprendre et à utiliser l'algorithme de jugement des nombres premiers en C++.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!