C++에서 소수 판단 알고리즘을 사용하는 방법

C++에서 소수 판단 알고리즘을 사용하는 방법

소수 판단은 알고리즘에서 흔히 발생하는 문제입니다. 주어진 숫자가 소수(소수)인지 판단해야 합니다. C++에서는 이 문제를 해결하기 위해 다양한 알고리즘을 사용할 수 있습니다. 이 기사에서는 두 가지 일반적인 소수 판단 알고리즘을 소개하고 해당 코드 예제를 제공합니다.

1. Brute force method (brute force method)
   Brute force method (Brute force method)는 주어진 숫자와 그 숫자보다 작은 모든 숫자에 대해 나머지 연산을 수행하는 것입니다. 어떤 숫자가 숫자로 나누어지면 그 숫자는 소수가 아니고, 그렇지 않으면 소수입니다.

다음은 주어진 숫자가 소수인지 확인하기 위해 무차별 대입 방법을 사용하는 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!