문제 정의
실행 시점에 사용자가 입력한 값 n을 기준으로, 1부터 n 사이에 존재하는 모든 소수(prime number)를 화면에 출력하는 C 프로그램을 작성하는 것이 이번 글의 목표입니다.
소수란 무엇인가?
소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다. 예를 들어 2, 3, 5, 7, 11 등이 소수에 해당하며, 4나 6처럼 1과 자신 외에 다른 약수를 가지는 수는 합성수라고 부릅니다.
해결 접근 방식
각 숫자가 소수인지 판별하려면 해당 숫자를 2부터 그 숫자의 절반까지 나누어 나머지가 0이 되는 경우, 즉 약수가 존재하는지 확인하면 됩니다. 약수가 하나도 없다면 그 수는 소수입니다. 이 원리를 for 루프로 구현하면 1부터 n까지의 모든 소수를 찾아낼 수 있습니다.
알고리즘
다음은 1부터 n 사이의 모든 소수를 출력하기 위한 알고리즘입니다.
1단계 – n 값을 입력받습니다.
2단계 – count 변수를 0으로 초기화합니다.
3단계 – i를 2부터 n까지 반복합니다.
a. j를 1부터 i까지 반복합니다.
b. 만약 i % j == 0이라면
c. count를 1 증가시킵니다.
d. count가 2와 같다면
e. i 값을 출력합니다.
흐름도
아래 흐름도는 위 알고리즘의 전체적인 처리 과정을 시각적으로 보여줍니다.
예제 코드
다음은 1부터 사용자가 입력한 값 n 사이의 모든 소수를 출력하는 C 프로그램입니다.
#include<stdio.h>
void main(){
int i, num, n, count;
printf("Enter the range: \n");
scanf("%d", &n);
printf("The prime numbers in between the range 1 to %d:",n);
for(num = 1;num<=n;num++){
count = 0;
for(i=2;i<=num/2;i++){
if(num%i==0){
count++;
break;
}
}
if(count==0 && num!= 1)
printf("%d ",num);
}
}
코드 설명
위 코드의 동작 과정을 단계별로 살펴보겠습니다.
첫째, scanf() 함수로 사용자에게 범위 값 n을 입력받습니다. 둘째, 바깥쪽 for 루프가 1부터 n까지 각 숫자를 차례대로 검사합니다. 셋째, 안쪽 for 루프는 현재 숫자(num)를 2부터 num/2까지 나누어 보며 약수가 존재하는지 확인합니다. 넷째, 약수가 발견되면 count를 증가시키고 break 문으로 내부 루프를 즉시 종료하여 불필요한 연산을 줄입니다. 다섯째, count가 0이고 num이 1이 아니라면 해당 숫자는 소수이므로 화면에 출력합니다.
실행 결과
위 프로그램을 컴파일하여 실행하고 범위로 50을 입력하면 다음과 같은 결과가 출력됩니다.
Enter the range:50
The prime numbers in between the range 1 to 50:
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
마무리
이처럼 for 루프와 조건문만으로도 소수 판별 로직을 손쉽게 구현할 수 있습니다. 참고로 더 큰 범위의 소수를 빠르게 구해야 한다면 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 활용하는 것이 효율적입니다.