이번 글에서는 사용자로부터 숫자 n을 입력받아, 1부터 n 사이에 있는 모든 소수(prime number)를 구한 후 역순(큰 수 → 작은 수)으로 출력하는 프로그램을 만들어 보겠습니다.
예를 들어 30을 입력하면, 30 이하의 소수인 29, 23, 19, 17, 13, 11, 7, 5, 3, 2가 큰 수부터 차례대로 출력됩니다.
입력 : 30
출력 : 29 23 19 17 13 11 7 5 3 2
알고리즘
전체적인 동작 흐름은 다음과 같습니다.
START
Step 1 -> 정수형 변수 n, i, j와 flag=0을 선언한다.
Step 2 -> 사용자로부터 숫자를 입력받아 n에 저장한다.
Step 3 -> i가 n부터 시작하여 1보다 클 때까지 1씩 감소하며 반복한다.
Step 3.1 -> j를 i/2부터 1 이상일 때까지 1씩 감소시키며 내부 반복문을 실행한다.
만약 i % j == 0 이고 j != 1 이라면
flag = 0 으로 설정하고 반복문을 탈출(break)한다.
그렇지 않으면
flag = 1 로 설정한다.
Step 3.2 -> 내부 반복문 종료
Step 4 -> flag가 1이면(소수라면) i를 출력한다.
Step 5 -> 외부 반복문 종료
STOP
동작 원리
핵심 아이디어는 간단합니다. 어떤 수 i가 소수인지 판별하려면, 2부터 i/2까지의 수 중에서 i를 나누어 떨어지게 하는 약수가 존재하는지만 확인하면 됩니다.
- 약수가 하나라도 발견되면 flag를 0으로 바꾸고 즉시 검사를 중단합니다. 이는 해당 수가 합성수(composite number)임을 의미합니다.
- i/2까지만 검사해도 충분한 이유는, i/2보다 큰 약수는 그 짝이 되는 약수가 반드시 2 미만이 되기 때문에 새로운 정보를 주지 않기 때문입니다.
바깥쪽 반복문은 n부터 2까지 거꾸로 진행하므로, 자연스럽게 소수가 역순으로 출력됩니다.
C 언어 예제 코드
#include <stdio.h>
int main(int argc, char const *argv[]) {
int n, i, j, flag = 0;
printf("Enter a number\n");
scanf("%d", &n);
for(i = n; i > 1; i--) {
for (j = i / 2; j >= 1; j--) {
if(i % j == 0 && j != 1) {
flag = 0;
break;
}
else
flag = 1;
}
if(flag == 1) {
printf("%d ", i);
}
}
return 0;
}
실행 결과
위 프로그램을 컴파일하여 실행하고 30을 입력하면 다음과 같은 결과를 얻을 수 있습니다.
Enter a number
30
29 23 19 17 13 11 7 5 3 2
성능 개선 팁
현재 코드는 각 수마다 최대 i/2번 나눗셈을 수행하므로 시간 복잡도가 O(n²)에 가깝습니다. 더 효율적으로 만들고 싶다면 다음 방법들을 고려해 볼 수 있습니다.
- 검사 범위 축소: i/2 대신 √i까지만 검사해도 소수 판별이 가능하므로 반복 횟수를 크게 줄일 수 있습니다.
- 에라토스테네스의 체: 2부터 n까지의 배열을 만들어 배수를 차례로 제거하는 방식으로, 많은 수의 소수를 한꺼번에 구할 때 훨씬 빠릅니다.