[BOJ] 1929 소수 구하기

(class 2)

- 1차 코드

#include<stdio.h>
int main()
{
	int start, end, i, j;
	
	scanf("%d %d", &start, &end);
	for (i = start; i <= end; i++) {
		int prime = 1;
		for (j = 2; j < i; j++) {
			if (i % j == 0) {
				prime = 0;
			}
		}
		if (prime == 1) {
			printf("%d\n", i);
		}
	}

}

실패 원인 : 시간 초과

  1차 코드는 실행은 잘 되었지만 시간 초과로 실패하였다. 따라서 코드의 효율성을 따질 필요가 있었다.

검색해본 결과, '에라토스테네스의 체' 방식을 사용해야 함을 알게되었다.

 

- 성공 코드

#include<stdio.h>
int arr[1000001];
int main()
{
	int start, end, i, j;

	scanf("%d %d", &start, &end);

	arr[0] = arr[1] = 1;

	for (i = 2; i <= end; i++) {
		for (j = 2 * i; j <= end; j += i) {
			if (arr[j] == 0) arr[j] = 1;
		}
	}

	for (i = start; i <= end; i++) {
		if (arr[i] == 0) printf("%d\n", i);
	}
	return 0;
}

<코드 설명>

  배열 arr을 만들어 소수이면 0, 아니면 1을 저장하도록 하였다. 입력값인 시작값(start)과 끝값(end)를 먼저 입력받았다.

i를 2부터 end까지 for문을 돌려주고 그 안에서 i의배수에 해당하는 것들을 차근히 지워나가주게 된다. 이처럼 원소 값이 1이 된 것들을 제외하고 나머지를 출력해준다.

 

<실행 결과>