C++での素数判定アルゴリズムの使い方

C で素数判定アルゴリズムを使用する方法

素数判定は、アルゴリズムの一般的な問題です。与えられた数値が素数 (素数) であるかどうかを判定する必要があります。番号）。 C では、この問題を解決するためにさまざまなアルゴリズムを使用できます。この記事では、2 つの一般的な素数判定アルゴリズムと、対応するコード例を紹介します。

1. ブルート フォース メソッド (総当たり法)
   ブルート フォース メソッド (暴力的メソッド) は、指定された数値と、その数値より小さいすべての数値を比較するという最も直接的なアルゴリズムです。剰余演算 数値を割り切れる数値がある場合、その数値は素数ではありませんが、そうでない場合は素数です。

以下は、指定された数値が素数かどうかを総当たりで判定する C コードの例です。

#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. エラトステネスのふるい
   エラ トストニーのふるいふるい法をベースにした素数判定アルゴリズムで、2から一定の範囲までのすべての数値の表を作成し、素数以外の数値を1つずつふるい落とすという考え方です。最後は素数です。

次は、エラトステネスの篩を使用して、指定された数値が素数かどうかを判断する C コードの例です。

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

上記は、2 つの共通の素数の C コードです。数値判定アルゴリズム コード例。このコードを実行すると、指定された数値が素数かどうかを判定できます。もちろん、どちらのアルゴリズムにも独自の長所と短所があり、特定のアプリケーション シナリオでは、実際の状況に基づいて適切なアルゴリズムを選択する必要があります。この記事が読者の C における素数判定アルゴリズムの理解と使用に役立つことを願っています。

以上がC++での素数判定アルゴリズムの使い方の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。