소수(prime number) 나열 알고리즘 최적화
배열 부분을 학습하며 소수 나열 알고리즘을 구현하고 최적화 해봤는데, 이해하기 쉽게 잘 정리해 올려보려고 한다.
소수(prime number)의 특성
소수는 자신과 1 이외의 정수로 나누어떨어지지 않는 정수이다.
예를 들면 2, 3, 5, 7 ... 등이 있다.
즉 n까지의 소수를 구하려면 반복문을 통해 3부터 n까지 수가 2부터 n-1까지의 정수로 나누어떨어지는지 체크해보면 된다.
#include <stdio.h>
int getPrime(int prime[], int n){
int speed = 0, value = 1, i, j;
prime[0] = 2;
printf("%d\n", prime[0]);
for(i = 3; i <= n; i++){
for(j = 2; j < i; j++){
speed++;
if(i%j == 0) break;
}
if(i == j){
prime[value] = i;
printf("%d\n", i);
value++;
}
}
return speed;
}
void main(){
int prime[500];
int n;
printf("n이하의 소수를 구하는 프로그램 입니다 n을 입력해주세요 : ");
scanf("%d", &n);
int speed = getPrime(prime, n);
printf("연산 횟수 : %d", speed);
}
--------------------------------------------------------------
1000 입력 시 결과
n이하의 소수를 구하는 프로그램 입니다 n을 입력해주세요 : 1000
2
3
5
7
11
13
17
...
967
971
977
983
991
997
연산 횟수 : 78022
이렇게 구현한 알고리즘을 개선 시키기 위해서는 연산 횟수를 줄여야 한다, 소수를 더 효율적으로 구하는 방법을 생각해보자.
알고리즘 개선 방안(1) - 소수의 배수들까지 확인할 필요가 없다
먼저 굳이 확인할 필요 없는 수의 연산을 제거할 것이다.
2나 3과 같은 소수들로 나누어떨어지지 않는다면 4, 6, 8, 9와 같은 소수들의 배수로도 2가 포함되어있기에 당연히 나누어떨어질 수 없다.
예를 들면 997이 2로 나누어떨어지지 않으니 4로도 8로도 400으로도 나눠떨어지지 않는다.
즉 이 논리를 쉽게 적으면, 2부터 n-1까지의 어떤 소수로도 나눠떨어지지 않는 수라고 소수의 범위를 축소할 수 있다.
이 원리로 알고리즘을 개선해보면
#include <stdio.h>
int getPrime(int prime[], int n){
int speed = 0, value = 1, i, j; //2를 넣고 시작하기에 value(요소의 개수)는 1개로 시작
prime[0] = 2;
printf("%d\n", prime[0]);
for(i = 3; i <= n; i++){
for(j = 0; j < value; j++){
speed++;
if(i%prime[j] == 0) break;
}
if(value == j){
prime[value++] = i;
printf("%d\n", i);
}
}
return speed;
}
void main(){
int prime[500];
int n;
printf("n이하의 소수를 구하는 프로그램 입니다 n을 입력해주세요 : ");
scanf("%d", &n);
int speed = getPrime(prime, n);
printf("연산 횟수 : %d", speed);
}
----------------------------------
같은 결과 값
연산 횟수 : 15620위와 같은 결과가 나오는데 여기서 추가적으로 2가 소수인걸 이미 알고있기에 조금 더 줄일 수 있을 것 같다.
알고리즘 개선 방안(2) - 우리는 2가 소수라는 사실을 안다
2의 배수인 짝수를 제외하고 홀수만을 대상으로 조사하기 위해 i++을 i+=2로 바꿔준다.
또한 홀수만 조사하므로 2를 확인할 필요가 없으니 j의 초기값도 j = 1로부터 시작한다.
#include <stdio.h>
int getPrime(int prime[], int n){
int speed = 0, value = 1, i, j; //2를 넣고 시작하기에 value(요소의 개수)는 1개로 시작
prime[0] = 2;
printf("%d\n", prime[0]);
for(i = 3; i <= n; i+=2){
for(j = 1; j < value; j++){
speed++;
if(i%prime[j] == 0) break;
}
if(value == j){
prime[value++] = i;
printf("%d\n", i);
}
}
return speed;
}
void main(){
int prime[500];
int n;
printf("n이하의 소수를 구하는 프로그램 입니다 n을 입력해주세요 : ");
scanf("%d", &n);
int speed = getPrime(prime, n);
printf("연산 횟수 : %d", speed);
}
----------------------------------
같은 결과 값
연산 횟수 : 14622
연산 횟수가 많이 줄었지만 더 줄이는 방법은 없을까 ? 아무래도 겹치는 곱셈 연산을 줄이면 될 것 같다.
알고리즘 개선 방안(3) - 대칭성을 이용해 한쪽만 체크하기
100을 약수로 나눠보면
2 * 50
..
4 * 25
..
10 * 10
..
25 * 4
..
50 * 2위와 같은 꼴의 형태가 되는데 여기서 규칙을 찾아보자면 중앙값인 10 * 10을 기준으로 양쪽이 대칭이 된다는 점이다.
즉 2와 4를 확인하면 50과 25는 확인할 필요가 없다는 것이 포인트다 !
이에 따라 100이 소수인지를 판단하려면 100의 제곱근인 10이 10보다 작은 소수들로 나누어떨어지는지를 확인하면 된다.
제곱근을 구하는것보다 제곱을 구하는게 간단하기에 이를 일반화시켜 요약하자면
prime[j]의 제곱이 n이하인 동안만 prime[j]로 나누어 떨어지는지 확인하면 되는것이다.
#include <stdio.h>
int getPrime(int prime[], int n){
int speed = 0, value = 0, i, j; //2를 넣고 시작하기에 value(요소의 개수)는 1개로 시작
prime[value++] = 2;
prime[value++] = 3; //2와 3을 소수에 대입 value++로 변경해 가독성 향상
printf("%d\n", prime[0]);
for(i = 5; i <= n; i+=2){
int flag = 0;
for(j = 1; speed++, prime[j] * prime[j] <= i; j++){
speed++;
if(i%prime[j] == 0){
flag = 1;
break;
}
}
if(flag == 0){
prime[value++] = i;
printf("%d\n", i);
}
}
return speed;
}
void main(){
int prime[500];
int n;
printf("n이하의 소수를 구하는 프로그램 입니다 n을 입력해주세요 : ");
scanf("%d", &n);
int speed = getPrime(prime, n);
printf("연산 횟수 : %d", speed);
}
----------------------------------
같은 결과 값
연산 횟수 : 3774
이처럼 곱셈 연산의 횟수도 포함시키기 위해 for 문에서 쉼표 연산자를 사용했다.
이렇게 쉼표 연산자를 사용한다면 speed++를 진행한 후 prime[j] * prime[j] <= i을 평가할 수 있다.
또한 같은 답을 얻는 알고리즘은 하나가 아니라는 사실과, 빠른 알고리즘은 더 많은 메모리를 요구한다는 점을 알게 되었다.
