C++에서 숫자가 소수인지 확인
이 기사에서는 C++에서 숫자가 소수인지 확인하는 몇 가지 방법을 설명합니다.
C++에서 숫자가 소수인지 확인하기 위해 시도 나누기 방법 사용
소수성 테스트는 주어진 숫자가 소수인지 여부를 결정하는 알고리즘의 이름입니다. 숫자가 소수인지 확인하는 간단한 해결책은 1에서 주어진 숫자까지 자연수를 반복하고 나눗셈에 나머지가 없는지 확인하는 것입니다.
몇 가지 통찰력이이 방법을 개선 할 수 있습니다. 첫 번째-정수n의 모든 제수는n/2보다 작거나 같으며 이는 검색 공간이 감소되었음을 의미합니다. 다음 예에서는validateInput함수를 구현하여 사용자로부터 정수를 가져와 해당 변수에 성공적으로 저장되었는지 확인합니다. 프로그램은 무한 루프로 실행되어 사용자에게 계속 번호를 요청한 다음 메시지를cout스트림으로 인쇄합니다.
#include <algorithm>
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::numeric_limits;
using std::string;
bool isPrime(unsigned long long &n) {
if (n <= 1) return false;
for (uint i = 2; i < n; ++i)
if (n % i == 0) return false;
return true;
}
template <typename T>
T &validateInput(T &val) {
while (true) {
cout << "Enter the natural number: ";
if (cin >> val) {
break;
} else {
if (cin.eof()) exit(EXIT_SUCCESS);
cout << "Enter a valid natural number!\n";
cin.clear();
cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
}
}
return val;
}
int main() {
unsigned long long num;
while (true) {
validateInput(num);
isPrime(num) ? cout << "Is Prime\n" : cout << "Is Not Prime\n";
}
exit(EXIT_SUCCESS);
}
상대적으로 최적화 된 방법을 사용하여 숫자가 소수인지 확인
모든 자연수에 대해 참인n의 제곱근보다 작거나 같은 제수 만 테스트하여 이전 방법을 계속 최적화 할 수 있습니다. 3보다 큰 모든 소수는6k+-1의 형태로 나타낼 수 있습니다. 여기서k는 0보다 큰 정수입니다. 또한 효율적인 방법이2및3값에 대한 숫자 분할 가능성을 테스트하는 것임을 의미합니다. 이전 조건이 주어진 숫자를 비 프라임으로 제거하지 않으면n의 제곱근보다 작은6k+-1형식의 모든 숫자를 테스트해야합니다. 터미널 인터럽트가 잡히면validateInput이while루프에서 중단됩니다 (예 : Ctrl+D).
#include <algorithm>
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::endl;
using std::numeric_limits;
using std::string;
template <typename T>
T &validateInput(T &val) {
while (true) {
cout << "Enter the natural number: ";
if (cin >> val) {
break;
} else {
if (cin.eof()) exit(EXIT_SUCCESS);
cout << "Enter a valid natural number!\n";
cin.clear();
cin.ignore(numeric_limits<std::streamsize>::max(), '\n');
}
}
return val;
}
bool isPrime(unsigned long long &n) {
if (n <= 3) return n > 1;
if (n % 2 == 0 || n % 3 == 0) return false;
for (int i = 5; i * i <= n; i += 6)
if (n % i == 0 || n % (i + 2) == 0) return false;
return true;
}
int main() {
unsigned long long num;
while (true) {
validateInput(num);
isPrime(num) ? cout << "Is Prime\n" : cout << "Is Not Prime\n";
}
exit(EXIT_SUCCESS);
}
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook