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

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

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

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

다음은 주어진 숫자가 소수인지 확인하기 위해 무차별 대입 방법을 사용하는 C++ 코드 예제입니다.

#include  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  #include  bool isPrime(int n) { if (n < 2) // 小于2的数都不是素数 return false; std::vector 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!