C++의 소수 생성기
이 빠른 프로그래밍 자습서는 간단하고 직관적인 방법과 효율적인 제곱근 방법을 사용하여 주어진 범위 내의 모든 소수를 생성하도록 안내합니다.
소수
소수는 1 또는 그 자체로만 나누어지는 숫자입니다. 예를 들어, 17은 1 또는 자기 자신으로만 나누어지는 숫자입니다. 소수 P에 대해 가능한 유일한 인수는 P * 1입니다.
소수 집합을 살펴보겠습니다.
Set of Prime Numbers = {2, 3, 5 , 7, 11, 13, 17, 23, .....,89, 97, .... }
C++에서는 이러한 시나리오를 코딩하고 일부 범위 내에서 소수를 생성할 수 있으며 숫자가 소수인지 여부도 확인할 수 있습니다.
C++에서 소수 생성
숫자가 소수인지 확인하는 논리는 해당 숫자의 절반까지의 모든 숫자로 모듈러스를 확인하는 것입니다. 숫자 중 하나에 대한 모듈러스가 0이면 숫자는 소수가 아닙니다. 그렇지 않으면 소수입니다.
가장 간단하고 직관적인 방법을 살펴보겠습니다.
#include <iostream>
using namespace std;
int main() {
int start = 0, end = 100, n;
bool ifPrime = true;
cout << "Prime numbers in between " << start << " and " << end
<< " are the following: " << endl;
while (start < end) {
ifPrime = true;
if (start == 0 || start == 1) {
ifPrime = false;
}
for (n = 2; n <= start / 2; ++n) {
if (start % n == 0) {
ifPrime = false;
break;
}
}
if (ifPrime) cout << start << ", ";
++start;
}
return 0;
}
위의 코드 세그먼트에서 start와 end라는 두 개의 변수를 사용했습니다. 0에서 100까지의 소수가 필요하기 때문에 start 변수는 0으로 초기화되고 end 변수는 100으로 초기화됩니다.
이 범위는 언제든지 변경하거나 사용자의 입력으로 가져올 수 있습니다.
시작에서 종료까지 루프를 만들었습니다. 그 루프에서 start 숫자가 이 숫자의 절반까지 숫자로 나누어지는지 확인하기 위해 또 다른 for 루프를 만들었습니다. 소수가 아닌 숫자 N의 경우 a*b와 같은 숫자 a와 b를 가진 인수만 있을 수 있기 때문입니다. 여기서 a<N/2 및 b<N/2.
따라서 내부 for 루프가 n이 start 값의 절반에 접근하도록 하면 루프가 종료되고 ifprime이 여전히 true이므로 25행에 숫자가 인쇄됩니다. 그러나 n 값이 start 값을 적절하게 나누면 19행의 조건이 true가 되어 ifprime을 false로 설정하고 for 루프를 종료합니다.
출력:
sqrt() 메서드를 사용하여 C++에서 소수 생성
앞에서 설명한 간단한 소수 계산 방법은 여전히 소수인지 여부를 확인하기 위해 숫자의 절반까지 나누어야 하므로 비효율적이었습니다. 그러나 수학적 사실을 이용하여 프로그램 실행 시간의 복잡성을 줄일 수 있습니다.
이 프로그램은 요인 a*b가 숫자 N과 같기 위해서는 a 또는 b가 N의 제곱근보다 작거나 같아야 한다는 사실에서 도움을 받습니다. 예를 들어, 36의 경우 가능한 요인 쌍은 (9*4), (18*2), (12*3), (6*6)이므로 모든 쌍에는 a가 있습니다. 또는 b는 36의 제곱근보다 작습니다.
따라서 숫자 N이 소수가 아니라고 승인하지 않으려면 N의 제곱근보다 작은 숫자로 나눌 수 있는지 여부만 확인하면 됩니다. 그렇지 않은 경우 숫자가 소수임을 의미합니다.
이제 시나리오를 코딩해 보겠습니다.
#include <math.h>
#include <iostream>
using namespace std;
int main() {
int start = 0, end = 100, n;
bool ifPrime = true;
cout << "Prime numbers in between " << start << " and " << end
<< " are the following: " << endl;
while (start < end) {
ifPrime = true;
if (start == 0 || start == 1) {
ifPrime = false;
}
for (n = 2; n <= sqrt(start); ++n) {
if (start % n == 0) {
ifPrime = false;
break;
}
}
if (ifPrime) cout << start << ", ";
++start;
}
return 0;
}
start에서 end까지 루프를 만들었고 해당 루프에서 숫자의 제곱근을 취하여 내부 루프의 잘림 숫자가 됩니다.
내부 루프는 현재 숫자가 제곱근까지의 숫자로 나눌 수 있는지 확인합니다. 그렇지 않은 경우 소수로 인쇄합니다.
출력: