[C언어] 소수 구하기
소수를 구하는 알고리즘은 여러 가지가 있다.
1 ~ 100까지의 소수를 출력하는 문제를 예로 들어서 알고리즘들을 간단히 정리해 보자.
소수(Prime Number)의 정의:
소수는 1보다 크고 그 숫자(자신)보다 작은 수 2개를 곱해서 만들 수 없는 수다.
-
2는 1보다 크고 2(자신)보다 작은 수(즉, 1)를 2개를 곱해서 만들 수 없으므로 소수이다.
-
10은 합성수(Composite Number: 1보다 크고 소수가 아닌 수)이다.
∵ 10 > 1, 2 × 5 = 10
문제: 1부터 100까지의 숫자 중 소수를 모두 출력해 보자.
[방법 0] 그냥 풀어보기! (가장 간단한 방법!)
소수를 어떻게 구할까?
간단히 생각해보면 어떤 수가 소수이려면 내가 구하고자 하는 수(n)가 1보다 크고 n보다 작은 수로 나눠지지 않으면 된다. 즉, n이 2 ~ n-1까지의 수로 나눠지는지 확인해보면 된다.
이것을 코드로 구현해보자.
#include <stdio.h>
int main()
{
//나눠 떨어졌는지 확인하기 위한 변수(Div: divisor 약수를 줄임)
int hasDiv = 0;
//1은 소수가 아니므로 생략
for (int n = 2; n <= 100; n++)
{
//(위에 제시한 방법) 1보다 크고 n보다 작은 숫자로 나눠 떨어지는지 확인
for (int div = 2; div < n; div++)
{
//나눠 떨어졌으면 1과 n사이의 수인 약수가 있다는 말이다. hasDiv변수를 true로 설정해주자.
if (n % div == 0) {
hasDiv = 1;
//이미 소수가 아닌 것을 확인했으므로 루프 탈출
break;
}
}
//약수가 없으면 소수이므로 출력
if (!hasDiv)
{
//소수 출력
printf("%d\n", n);
}
//hasDiv 초기화
hasDiv = 0;
}
return 0;
}
[방법 1] 반까지만 나눠보기
위의 소수를 판별하는 과정을 다시 살펴보자. 만약 16(n = 16인 경우)을 소수인지 판별한다고 하면 우리는 16을 1과 16 사이의 모든 수(2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15)로 나눠 볼 것이다.
이때, 제일 처음에 2로 먼저 나눠보는데 16 = 2 * 8이다. 그런데 16은 동시에 8 * 2이므로 이것은 8로 나눠보는 경우랑 겹친다.
n이 다른 경우도 모두 동일하다. n = 90일 때를 보자. 90 = 2 * 45, 90 = 45 * 2이므로 45이상의 수를 확인하는 것은 더 이상 의미가 없다는 것을 확인할 수 있다.
다르게 생각해보면 45가 최소의 수 약수인 2를 가질 수 있는 최대치이므로 45 미만의 수까지만 나눠봐도 되는 것이다.
따라서, 45이하의 숫자만 약수가 될 수 있다는 것을 확인할 수 있다.
n이 홀수일 때는 어떻게 해야 할까?
9(n = 9인 경우)를 소수인지 판별하는 경우를 생각해 보자.
n = 9이면 n/2 = 4.5이다. 우리는 이제 소수인지 확인하고자 하는 의 숫자의 반(즉, 9/2 = 4.5) 이상을 확인하는 것은 겹치므로 그 숫자들로 나눠보는 것은 의미가 없다는 것을 안다.
그런데 9/2 = 4.5인데 어디까지 나눠야 할까?
간단하게, 4.5라는 자연수는 존재할 수 없으므로 4까지만 나눠보면 된다.
이것을 코드로 구현해보자.
[방법 0]의 2번째 for문의 조건문(div < n → div <= n/2)만 수정해주면 된다.
(참고로, <=의 =은 홀수로 나눠서 숫자가 작아질 때를 위해 넣었다.)
#include <stdio.h>
int main()
{
//나눠 떨어졌는지 확인하기 위한 변수(Div: divisor 약수를 줄임)
int hasDiv = 0;
//1은 소수가 아니므로 생략
for (int n = 2; n <= 100; n++)
{
//(위에 제시한 방법) 1보다 크고 n/2보다 작은 숫자로 나눠 떨어지는지 확인
for (int div = 2; div <= n/2; div++)
{
//나눠 떨어졌으면 1과 n사이의 수인 약수가 있다는 말이다. hasDiv변수를 true로 설정해주자.
if (n % div == 0) {
hasDiv = 1;
//이미 소수가 아닌 것을 확인했으므로 루프 탈출
break;
}
}
//약수가 없으면 소수이므로 출력
if (!hasDiv)
{
//소수 출력
printf("%d\n", n);
}
//hasDiv 초기화
hasDiv = 0;
}
return 0;
}
[방법 2] 제곱근까지만 나눠보기
사실은 [방법 1]보다 더 효율적인 방법이 있다. 반까지만 나눠 보는 것이 아니라 제곱근까지만 나눠보면 된다.
이것은 다음의 예시를 보면 이해하기 쉽다.
36(n = 36인 경우)을 소수인지 판별하는 경우를 생각해 보자.
36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36 이다.
위의 약수를 살펴보면 핑크색(6 이후의 약수들)은 초록색( + 6은 6자신)과 대응된다.
대응되는 약수: (2, 18) (3, 12) (4, 9) (6, 6)
대응되는 수들을 다시 한번 나눠서 확인해줄 필요가 없다.
그러므로 36의 제곱근(즉, 6) 이상은 확인해줄 필요가 없다.
제곱근이 자연수가 아닌 경우는 어떻게 해야 할까?
10(n = 10인 경우)을 소수인지 판별하는 경우를 생각해 보자. 우리는 이제 10의 제곱근 이후의 숫자들은 약수들이 대응되므로 그 숫자들로 나눠보는 것은 의미가 없다는 것을 안다.
그런데 제곱근은 약 3.1622인데 어디까지 나눠줘야 할까?
3.1622와 같은 자연수는 나올 수 없으므로 3까지만 나눠보면 된다.
이것을 코드로 구현해보자.
[방법 0]의 2번째 for문의 조건문(div < n → div <= sqrt(n))만 수정해주면 된다.
#include <stdio.h>
#include <math.h>
int main()
{
//나눠 떨어졌는지 확인하기 위한 변수(Div: divisor 약수를 줄임)
int hasDiv = 0;
//1은 소수가 아니므로 생략
for (int n = 2; n <= 100; n++)
{
//(위에 제시한 방법) 1보다 크고 sqrt(n) 이하의 숫자로 나눠 떨어지는지 확인
for (int div = 2; div <= sqrt(n); div++)
{
//나눠 떨어졌으면 1과 n사이의 수인 약수가 있다는 말이다. hasDiv변수를 true로 설정해주자.
if (n % div == 0) {
hasDiv = 1;
//이미 소수가 아닌 것을 확인했으므로 루프 탈출
break;
}
}
//약수가 없으면 소수이므로 출력
if (!hasDiv)
{
//소수 출력
printf("%d\n", n);
}
//hasDiv 초기화
hasDiv = 0;
}
return 0;
}
[방법 3] 에라토스테네스의 체
위의 [방법 0], [방법 1], [방법 2]들은 특정한 숫자 하나(n)에 대해 소수인지 확인하는 방법들이다.
그래서 1부터 100까지의 숫자를 모두 소수인지 확인하려면 n을 (1~100까지 1씩) 증가시키면서 100번 반복문을 돌려서 위의 알고리즘들을 활용해서 소수인지 확인했다.
극단적으로 1 ~ 5000000까지의 소수를 확인하려면 얼마나 오래 걸릴까..?
([방법 2]의 코드에서 printf를 주석 처리하고 실행해보니 4초 정도 걸렸다)
1 ~ 5000000까지의 소수를 확인하는 경우, 더 효율적인 방법은 없을까?
5000000번 확인하지 않고 1 ~ 5000000을 모두 동시에 확인하는 방법은 없을까?
에라토스테네스의 체가 그 방법이다.
에라토스테네스의 체는 [방법 2]를 이해했다면 이해하기 더 쉽다.
(구글 이미지에 에라토스테네스의 체를 검색해보면 바로 이해가 된다)
에라토스테네스의 체는
1. 소수인지 판별하고자 하는 숫자들이 주어졌다면 일단 주어진 숫자들을 모두 나열하고 1을 제외한 모든 숫자를 소수라고 가정한다.
2. 나열된 숫자들 중 소수이면서 가장 작은 숫자부터 시작해서 (자기 자신을 제외한) 그 숫자의 배수(소수가 아니므로)들을 지운다(소수가 아니라는 것을 저장한다고 봐도 된다).
3. 2. 를 소수들만 남을 때까지 반복한다.
이때, 내가 2부터 시작해서 n까지의 배수들을 지웠다면 2 ~ floor(n의 제곱)까지의 숫자들을 모두 소수들만 남았다는 것을 알 수 있다. 따라서, 내가 1~100까지의 숫자가 소수인지 확인하고자 한다면 (11의 제곱 > 100이므로) 11의 배수 아래(즉, 10)까지만 지워주면 된다.
( ∵ [방법 2]를 떠올려 보자! [방법 2]에서 k가 소수인지 확인하려면 k의 제곱근까지 확인하면 되므로 2부터 (k의 제곱근)의 배수를 모두 제거했다면 k까지는 모두 소수가 아닌 것을 알 수 있을 것이다)
당황하지 말고 구글에 에라토스테네스의 체를 검색해서 눈으로 보고 오자 ㅎㅎ. 설명을 잘못하겠다...ㅠㅠ.
에라토스테네스의 체를 이용하여 1 ~ 100까지의 숫자 중 소수를 출력해보는 코드를 구현해보자.
(MAX_TARGET으로 구하고자 하는 숫자의 범위를 주었다.)
#include <stdio.h>
#include <math.h>
#define MAX_TARGET 100
int main()
{
//1 ~ 100을 체크하기 위한 배열, 0번째 인덱스는 사용하지 않았다.
char isPrimeNumber[MAX_TARGET+1];
//1은 소수가 아니라 가정
isPrimeNumber[1] = 0;
//1외에는 모두 소수라고 가정
for (int i = 2; i < MAX_TARGET+1; i++)
{
isPrimeNumber[i] = 1;
}
//에라토스테네스의 체
for (int n = 2; n <= floor(sqrt(MAX_TARGET)); n++)
{
//n이 소수가 아닌 경우 continue
if (!isPrimeNumber[n])
{
continue;
}
//소수인 n의 배수들 모두 제거
for (int mult = 2; n * mult <= MAX_TARGET; mult++) {
isPrimeNumber[n*mult] = 0;
}
}
//에라토스테네스의 체를 이용하여 소수들만 남은 배열 출력
for (int i = 1; i < MAX_TARGET+1; i++)
{
//소수인 숫자들 모두 출력
if (isPrimeNumber[i])
{
printf("%d\n", i);
}
}
return 0;
}그럼 에라토스테네스의 체로 1 ~ 5000000까지의 소수를 확인하려면 얼마나 오래 걸릴까?
위의 코드에서 printf를 주석 처리하고 실행해보니 2초 정도 걸렸다.
(잘못된 것이 있다면 댓글로 알려주세요!!)
Icons made by Smashicons from www.flaticon.com
thanks to. 상민