소수(Prime Number)
IMPORTANT
소수(Prime Number, 素數)의 표준 발음은 국어 사전에서 제시한 대로 소쑤입니다.
소수 정의
수학 또는 알고리즘 학문에서 정의된 소수는 다음과 같습니다. 소수는 발음할 때 소쑤로 발음합니다.
소수(Prime Number):
- 자연수 중에서 1과 자기 자신만을 약수로 가지는 자연수
- 양의 약수가 1과 자기 자신 뿐인 1보다 큰 자연수로 정의
- 2는 소수: 1과 2만을 약수로 가짐
- 5는 소수: 1과 5만을 약수로 가짐
- 6은 소수가 아님: 1, 3, 6을 약수로 가짐
- 2, 5, 7, 11, 13, 17, …
소수 알고리즘 순서도
다음은 소수 알고리즘에 대한 의사 코드를 표현한 순서도입니다.
그림: 소수 알고리즘
소수 판별하기
표준 입력으로 정수 하나를 입력 받아서 소수인지 아닌지 판별하는 프로그램을 작성하겠습니다.
여러 가지 방법이 있겠지만 가장 간단한 방법은 2부터 해당 수까지 나머지값을 구해서 나머지값이 0일때 나눈 수가 해당 수라면 소수이고 그렇지 않으면 소수가 아님을 판단하면 됩니다.
코드: prime_number_docs.c
//[?] 특정 수를 입력 받아서, 소수인지 아닌지 판별하는 프로그램
// - 5는 소수: 1과 5만을 약수로 가짐
// - 6은 소수가 아님: 1과 6만이 아닌 추가로 2와 3을 약수로 가짐
// - 2부터 해당 수까지 나머지값을 구해서 나머지값이 0일때 나눈 수가 해당 수라면 소수
#define _CRT_SECURE_NO_WARNINGS // scanf 보안 경고로 인한 컴파일 에러 방지
#include <stdio.h>
int main(void)
{
/// <summary>
/// 소수(Prime Number): 자연수 중에서 1과 자기 자신만을 약수로 가지는 자연수
/// </summary>
//[1] Input
int i;
int number;
scanf("%d", &number);
//[2] Process: Prime Number(2부터 n까지 나누어 떨어지는 수가 발생할 때까지 반복)
i = 1;
do
{
i = i + 1; // 2부터 n까지 비교
printf("%d %% %d = %d\n", number, i, number % i);
} while (number % i != 0); // 소수는 number로만 나누어 떨어짐
//[3] Output
if (number == i)
{
printf("소수임\n");
}
else
{
printf("소수 아님\n");
}
return 0;
}
실행 결과
7
7 % 2 = 1
7 % 3 = 1
7 % 4 = 3
7 % 5 = 2
7 % 6 = 1
7 % 7 = 0
소수임
6
6 % 2 = 0
소수 아님
13
13 % 2 = 1
13 % 3 = 1
13 % 4 = 1
13 % 5 = 3
13 % 6 = 1
13 % 7 = 6
13 % 8 = 5
13 % 9 = 4
13 % 10 = 3
13 % 11 = 2
13 % 12 = 1
13 % 13 = 0
소수임
동영상 강의
표준 입력으로부터 입력한 수를 1을 제외한 2부터 n까지 반복하면서 나누면서 나머지 값을 구했을 때 0이 되는 시점이 자기 자신이 아닌 다른 수라면 중간에 약수가 있다는 의미입니다.
이 방법을 사용하여 최종 나누어 떨어진 수가 입력한 수와 같다면 소수이고 그렇지 않다면 소수가 아님을 판단할 수 있습니다.
코드에서는 소수 알고리즘을 do while 반복문을 사용했는데요. 여러분들이 직접 for 반복문으로도 만들어보고 실행해보세요.
특정 범위의 소수 합계 구하기
특정 범위의 소수 합계를 구하는 여러 가징 방법 중 하나를 나타내는 참고용 순서도입니다.
그림: 소수의 합계
다음 코드는 주어진 범위에서 소수를 찾고 해당 소수의 개수 또는 합계를 구하는 프로그램입니다.
코드: prime_number_sum_docs.c
//[?] 정수 하나를 입력 받아, 2부터 해당 수까지에 존재하는 모든 소수를 찾아서 출력
// 예: 2 ~ 20까지의 정수: 2, 3, 5, 7, 11, 13, 17, 19 -> 8개
#define _CRT_SECURE_NO_WARNINGS // scanf() 보안 경고에 따른 컴파일 에러 방지
#include <stdio.h>
int main(void)
{
//[1] Input
int sum = 0; // 소수 합계
int count = 0; // 소수 개수
int sw = 1; // 소수(1)인지를 확인하는 스위치 변수(flag)
int number = 0; // 2 ~ number까지의 수 중 소수를 구함
scanf("%d", &number);
//[2] Process: Prime Number -> Count
for (int i = 2; i <= number; i++) // 2부터 n까지 반복하면서 소수 판별
{
sw = 1; // 일단 모든 반복마다 소수로 놓고 시작
// 2부터 현재수(i) - 1까지 나누었을 때 나누어 떨어지면 소수가 아님
for (int j = 2; j < i; j++)
{
if (i % j == 0)
{
sw = 0; // 소수가 아님
break;
}
}
if (sw) // 소수이면 합계 또는 개수 계산
{
printf("%d\t", i);
count++; // COUNT
sum = sum + i; // SUM
if (count % 5 == 0)
{
printf("\n"); // 줄바꿈
}
}
}
printf("\n");
//[3] Output
printf("2부터 %d까지의 소수의 개수: %d\n", number, count);
printf("2부터 %d까지의 소수의 합계: %d\n", number, sum);
return 0;
}
실행 결과
7
2 3 5 7
2부터 7까지의 소수의 개수: 4
2부터 7까지의 소수의 합계: 17
20
2 3 5 7 11
13 17 19
2부터 20까지의 소수의 개수: 8
2부터 20까지의 소수의 합계: 77
100
2 3 5 7 11
13 17 19 23 29
31 37 41 43 47
53 59 61 67 71
73 79 83 89 97
2부터 100까지의 소수의 개수: 25
2부터 100까지의 소수의 합계: 1060
바깥쪽 for 반복문의 다음 코드를 통해서 시작과 끝의 범위를 지정하여 반복합니다.
for (int i = 2; i <= number; i++) {}
스위치 변수인 sw를 무조건 1로 초기화하여 일단은 반복되는 모든 수를 소수로 두고 시작합니다.
sw = 1; // 일단 모든 반복마다 소수로 놓고 시작
안쪽 첫 번째 for 반복문에서는 다음 두 가지 모양 중 하나를 사용하여 소수인지를 나타내는 i 인덱스 변수보다 1 작은 반복을 진행합니다.
for (int j = 2; j < i; j++) {}
for (int j = 2; j <= i - 1; j++) {}
만약, i가 j로 나누어 떨어진다면, 즉, 중간에 다른 약수가 존재한다면 i는 소수가 아님을 알 수 있습니다. 그러면 스위치 변수를 1(true)에서 0(false)으로 변경하고 소수 판별 for 반복문을 빠져나옵니다.
if (i % j == 0)
{
sw = 0; // 소수가 아님
break;
}
만약 바깥쪽 for 반복문의 하나의 반복이 끝나고 소수가 확정되면 이 소수에 대한 합계 또는 개수를 계산합니다.
if (sw) // 소수이면 합계 또는 개수 계산
{
count++; // COUNT
sum = sum + i; // SUM
}