[C언어]2와 100사이에 있는 모든 소수(prime number)를 찾는 프로그램 : 쉽게 풀어쓴 C언어 Express 7장

쉽게 풀어쓴 C언어 Express 7장 7번 문제를 풀어보자.

 

---

2와 100사이에 있는 모든 소수(prime number)를 찾는 프로그램을 작성하라. 정수가 소수가 되려면 1과 자기 자신만을 약수로 가져야 한다.

 

 HINT  : 소수의 약수는 1과 자기자신뿐이다. 따라서 1부터 자기 자신 사이에 약수가 하나라도 있다면 소수가 아니다.

---

 

 

풀이

이전에 boolean의 개념에 대해 배웠었더라면 true와 false를 이용해도 됐을 것이다. 그러나 boolean에 대해 아직 배우지 않아 stdbool.h 헤더파일을 사용할 수 없으므로, 소수인지 아닌지를 구분하는 것을 1과 0으로 하자.

while(1)에서도 1을 작성하면 무한루프를 돌듯이, 보통 1이 true를 뜻하고 0이 false를 뜻한다.

i로 2부터 1씩 증가하면서 숫자 하나씩 모두 소수인지 아닌지를 판단할 것이다.

그런데 소수를 판단하려면 그 숫자 i가 자기자신보다 작은 숫자들로 나누어 떨어지면(나머지가 0이면) 안될 것이다. 그러므로 반복문을 하나 더 만들어 j가 2부터 i까지 나머지연산자 %를 수행하도록 해줘야 할 것이다. 나머지연산자를 수행한 값이 0이면 나누어떨어졌다는 뜻으로 소수가 아니므로, 소수가 아니라는 의미의 isPrime=0을 주고 반복문을 탈출하자.

반복문을 탈출하면 isPrime이 1인지 0인지를 판단하여 출력할지말지 정하자.

 

 

코드

#include <stdio.h> 
int main(void) {

	int i, j, isPrime;

	for (i = 2; i <= 100; i++) {
    	//기본적으로 소수라고 가정. 소수가 아닐 때만 0으로 바꾸어주면 되기 때문
		isPrime = 1;
		for (j = 2; j < i; j++) {
			if (i % j == 0) {
				isPrime = 0;	//소수가 아닌 경우
				break;
			}
		}
		if (isPrime == 1) {	//소수일 경우에만 출력한다.
			printf("%d ", i);
		}
	}

	return 0;
}

 

 

실행결과

 

 

 

추가 풀이

사실 소수인지를 판단하는 j 반복문을 자기자신인 i까지 돌려줄 필요는 없다.

예를 들어, 숫자 15가 소수인지를 판단한다고 할 때, j=2 부터 반복문을 시작할 것이다.

15의 약수는 1,3,5,15 인데, 15의 절반인 약 7~8 이하로만 소수를 판단해도 되는 것이다.

위와 같이 15의 절반을 기준으로 7 이하에 나누어 떨어지는 약수가 있다면 무조건 소수가 아닌 것으로 판단할 수 있다는 뜻이다. 동시에, 절반인 7 이하에 나누어 떨어지는 약수가 없다면 무조건 소수인 것으로 판단한다는 것이다.

15와 같이 소수가 아닌 숫자는 for 문을 채 다 돌기도 전인 j=3에서 break로 탈출해버릴 것이다.

그러나 101과 같이 소수인 숫자는 약수가 없으므로 j=100 까지 100번이나 반복문을 돌 것이다. 이것은 심각한 성능 저하를 초래할 수 있는 코드이다.

 

그러므로, j의 범위를 j<i 가 아닌, j <= i/2 로 설정해주자.

 

#include <stdio.h> 
int main(void) {

	int i, j, isPrime;

	for (i = 2; i <= 100; i++) {
		isPrime = 1;
		for (j = 2; j <= i/2; j++) {
			if (i % j == 0) {
				isPrime = 0;
				break;
			}
		}
		if (isPrime == 1) {
			printf("%d ", i);
		}
	}

	return 0;
}

 

조금 더 효율이 높아진 코드를 작성할 수 있다.