소수 구하기 - 바로 실행해보면서 배우는 C언어

반복문, 조건문 응용해 소수 구하는 코드 작성하기

문제 : 값을 입력받아서 입력받은 값 미만의 수 중 소수를 출력한다. 소수의 갯수는 최대 100개로 제한한다.

 

배열에 담지 않고 바로 출력하기

#include <stdio.h>
int main() {
	int num;
	scanf("%d", &num);
	int i;
	int j;
	
	for(i=2; i<=num; i++) {
		for(j=2; j<i; j++) {
			if(i%j == 0) { 
				break;
			}
		}
		if(i==j) {
			printf("%d ", i);
		} 
	}
	return 0;
}

1. 소수는 1과 자기자신을 제외하고 어떤 수로도 나눠지지 않는 수이다.(2, 3, 5, 7, 13, 17, 19... 등이 있다. 1은 소수가 아님)

1~20 사이의 정수 중 소수를 구하려면(num=20을 입력받았을 때)

for문으로 1부터 20까지 돌면서 소수가 있는지 확인하고, 소수가 있다면 출력하면 된다.

단, 1은 소수가 아니므로 제외해야 한다. 따라서 바깥쪽 반복문의 초기값 i는 0이나 1이 아니라 2부터 시작한다. 

또한 num 자체가 소수일 수도 있으므로(입력받은 num이 2, 3, 5, 7, ... 등 소수인 경우)

바깥쪽 반복문의 종결조건은 i<num이 아니라 i<=num으로 num까지 포함시켜야 한다. 

 

2. 소수인지 확인하는 방법은 다음과 같다.

예를 들어 i=8이라면, 8보다 작은 자연수(1과 8 자기자신을 제외한 2~7사이의 숫자)로 8을 나눴을 때, 나누어 떨어지는 수가 있는지(8%j == 0) 확인하면 된다.

나누어 떨어지는 수가 있다면 8은 소수가 아니다.

만약 2~7까지 모두 확인했는데 나누어 떨어지는 수가 없다면, 8은 소수이므로 printf로 출력하면 된다. 

 

소수인지 확인하는 로직은 안쪽 반복문에서 작성했다.

for(j=2; j<i; j++) {
	if(i%j == 0) { 
		break;
	}
}

i=8일 때, 

8을 2~7까지 차례대로 나누어보면서 나머지가 0인지(나누어 떨어지는지) 확인한다.

만약 나머지가 0이라면, break문을 실행해 안쪽 반복문을 빠져나온다.

-> 나누어 떨어지는 숫자가 없다면(8이 소수라면) 종결조건을 만족할 때까지(j=7) 반복문을 다 돌고, 마지막으로 j가 1증가(j++)한 다음 반복문을 빠져나오기 때문에

변수 j의 값은 최종적으로 8이 된다. (i==j)

-> 나누어 떨어지는 숫자가 있다면(8이 소수가 아니라면) 반복문을 다 돌지 못하고(종결조건(j<8)까지 도달하지 못하고) 중간에 빠져나와

변수 j의 값이 최종적으로 8 미만의 값이 된다. (j<i)

 

=> 안쪽 반복문을 빠져나온 이후 j의 값이 i와 같은지 아닌지 확인함으로써

i가 소수인지 아닌지 확인할 수 있다.

 

따라서 안쪽 반복문을 빠져나온 뒤 조건문을 사용해

if(i==j) {
	printf("%d ", i);
} 

위와 같이 i==j인지 확인한다. i==j라면 i는 소수이기 때문에 printf로 출력하고,

그렇지 않다면 바깥쪽 반복문을 계속 진행해 i 다음 숫자(i++)가 소수인지 확인한다.

 

※ 안쪽 반복문의 카운터 변수 j를 안쪽 반복문을 빠져나온 후에도 사용해야하기(i==j 비교) 때문에

j를 반복문 안에서 선언하지 않고, 반복문 밖에서 선언해 반복문을 빠져나온 후에도 사용할 수 있도록 했다.

참고로 바깥쪽 반복문의 카운터 변수 i는 반복문 안에서만 사용되고 있기 때문에 반복문 안에서 선언해도 되고 반복문 밖에서 선언해도 된다. 

 

배열에 담아 출력하기

원래 문제의 의도대로 구한 소수들을 배열에 담은 후 출력하는 방법이다. 

#include <stdio.h>
int main() {
	int num;
	scanf("%d", &num);
	
	int length = 1;
	
	int i;
	int j;
	
	for(i=2; i<=num; i++) {
		for(j=2; j<i; j++) {
			if(i%j == 0) { 
				break;
			}
		}
		if(i==j) {
			length++;
			int arr[length];
			arr[length-1] = i;
			printf("%d ", arr[length-1]);
		} 
	}
	
	return 0;
}

 

배열의 길이(length)를 변수로 따로 선언한다. 마지막 요소로 null값을 담아 어디까지 출력할지 나타내기 위해서 배열의 길이는 1로 초기화했다.

소수를 구했다면, 배열의 길이를 1 늘리고(length++), 

늘린 길이를 이용해 배열을 선언한 다음, 구한 소수를 배열의 요소로 추가한다.

배열의 요소로 추가할 때는 배열의 인덱스(길이-1)를 이용했다.

그리고 추가한 배열 요소를 바로 불러와서 출력한다. 

 

아쉬운 점

- 내가 아직 배열을 잘 못 다뤄서 그런건지, 배열에 담아 출력하는 코드는 약간 지저분하게 됐다.

 

- 문제의 힌트를 보면 int i, j를 반복문 밖에서도 사용할 수 있게 선언하라고 했는데

내 코드에서 i의 경우 반복문 밖에서 선언하지 않아도 정답을 구할 수 있다. i를 반복문 밖에서도 사용해야하는 방식으로 풀려면 어떻게 해야하는지 고민해봤는데 잘 모르겠다.

 

- 소수의 개수 제한 조건은 작성하지 않았다. 

테스트 케이스가 num = 10, num = 30인 경우밖에 없어서 제대로 실행되었지만

입력된 숫자가 더 큰 경우 length >102인 경우 출력을 중단하거나 배열에 요소 추가를 하지 않도록 제한하는 코드가 추가되어야할 것 같다.