如何使用C++中的質數判斷演算法

如何使用C 中的質數判斷演算法

素數判斷是演算法中常見的問題，它要求判斷給定的數是否是質數（質數）。在C 中，我們可以使用不同的演算法來解決這個問題，本文將介紹兩種常見的質數判斷演算法，並給出對應的程式碼範例。

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開始到給定範圍的所有數的表格，然後逐個篩除非素數的數，最終留下的就是素數。

以下是使用埃拉托斯特尼篩法判斷一個給定數是否是質數的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;
}

以上是兩種常見的質數判斷演算法的C程式碼範例，透過執行這些程式碼，我們可以判斷一個給定的數是否是素數。當然，這兩種演算法都有自己的優缺點，在具體的應用場景中需要根據實際情況來選擇適合的演算法。希望本文對讀者理解和使用C 中的質數判斷演算法有所幫助。

以上是如何使用C++中的質數判斷演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！