저는 이번 정융탐의 주제로 소수 판별법을 선택했습니다. 제가 구현해본 소수 판별법의 종류는 2가지로 2가지 소수판별법은 서로 다른 특징을 가지고 있습니다.
일단 개념부터 설명해드리겠습니다.
소수란 1보다 큰 자연수 중에서 1과 자기 자신만을 약수로 가지는 자연수입니다. 예를 들어 6은 약수로 1 2 3 6을 가지기 때문에 소수가 아닌 합성수이고 7은 약수로 1, 7을 가지기 때문에 소수입니다.
일단 제가 첫번째로 시도한 방법은 간단한 알고리즘을 가지고 있습니다.
2보다 큰 자연수 n에 대하여 2부터 n-1까지의 모든 수로 나누어서 만약 나누어떨어지는 수가 하나라도 존재하면 소수가 아닌 것이라는 알고리즘을 계획했습니다.
코드는 다음과 같습니다.
#include <stdio.h>
int main()
{
int n, i;
int det_prime = 1; // 소수인지 알려주는 값을 정하였고 처음 값을 소수라고 정하였다.
printf("수를 입력하세요: ");
scanf("%d", &n);
if (n < 2) { // n이 2보다 작으면 소수가 아니다.
det_prime = 0;
}
for (i = 2; i < n; i++) { // n-1번 반복문을 돌린다.
if (n % i == 0) { // n이 i로 나눠지는지 확인한다.
det_prime = 0; // 나눠진다면 소수가 아니라는 것이므로 코드를 벗어난다.
break;
}
}
if (det_prime) { // 1은 true 0은 false이므로 조건문을 사용하였다.
printf("%d는 소수입니다.\n", n); // 값이 1면 소수를 나타낸다.
} else {
printf("%d는 소수가 아닙니다.\n", n); // 값이 0이면 소수가 아니다.
}
}이런식으로 간단한 반복문과 조건문을 통해 소수를 판별하는 코드를 생각해봤습니다.
이 코드의 순서도는 다음과 같습니다.
위 코드의 단점은 무엇일까요? 바로 2부터 n-1까지 반복문을 실행해야 해서 알고리즘 복잡도가 높다는 것과 특정한 수가 소수인지만 판별할 수 있다는 것입니다.
그렇다면 특정한 범위를 주었을때 그 구간안에 있는 소수가 무엇인지 알 수 있고 시간 복잡도를 줄이는 방법은 무엇일까요?
그것은 바로 에라토스테네스의 체를 이용한 방법입니다.
에라토스테네스의 체는 소수를 찾는 방법으로
1. 소수를 찾을 구간을 설정한다.
2. 2부터 최대값까지의 수를 나열한다.
3. 남은 수 중에서 아직 남아있는 가장 작은수 k를 찾는다.
4. 남은 수 중에서 k의 배수를 제거한다.
5. 위의 3~4번의 과정을 반복하여 특정한 구간에서의 소수를 남긴다.
의 과정을 갖고 있습니다.
이를 코드로 나타내보면 다음과 같습니다.
#include <stdio.h>
void che(int n) {
int prime[n]; // prime이라는 배열을 선언
for (int i = 2; i <= n; i++) {
prime[i] = 1; // 배열에 있는 모든 수를 소수로 초기화
}
for (int p = 2; p*p <= n; p++) {
if (prime[p] == 1) { // p가 소수일때
for (int i = p*p; i <= n; i += p) { // p의 배수들을 소수가 아닌 것으로 변경시킴
prime[i] = 0; // 소수가 아닌 값
}
}
}
// 소수라고 설정해 놓은 값들을 가지는 배열의 인덱스를 보고 소수를 출력
for (int i = 2; i <= n; i++) {
if (prime[i] == 1) {
printf("%d ", i); // 소수를 출력
}
}
}
int main() {
int n;
printf("n값을 입력하세요: ");
scanf("%d", &n);
che(n);
}이 코드는 prime이라는 배열을 선언해서 범위를 정해주고 그 안의 모든 값을 소수를 나타내는 값(1)로 초기화 한 뒤에 소수의 배수들을 소수가 아닌 값(0)으로 초기화하여 배열을 저장한 뒤에 배열에서 1을 찾아서 1을 나타내는 배열의 인덱스를 뽑음으로써 소수를 출력하는 코드입니다.
여기서 생각해볼만 한 점은 반복문을 n의 제곱근까지만 반복했다는 것입니다.
그 이유는 소수는 자신과 자신의 제곱근 사이에 약수가 존재하지 않기 때문입니다.
예를 들어서, 36이라는 수가 있을 때, 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36 입니다. 이때 36의 제곱근은 6입니다. 6보다 큰 약수인 9, 12, 18, 36은 모두 6보다 작은 약수인 1, 2, 3, 4, 6의 배수입니다. 따라서 6보다 큰 약수는 생각하지 않아도 되는 것입니다.
위와 같이 반복문을 n의 제곱근만큼만 실행시키는 것은 코드의 시간 복잡도를 줄여주게 해줍니다.
위 내용은 이 코드의 알고리즘 순서도입니다.
이상으로 소수 판별법에 대한 글을 마치겠습니다.
