1929번 소수 구하기(C)

11수 만에 성공했다.

분명 나는 맞게 했다고 생각했는데 왜 계속 틀렸다고 하는지

아직도 사실 모르겠다.

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

 

사전지식

% 연산을 모든 숫자들에게 행하여 0이 나오면 소수가 아니다, 이런 방식으로 하면 시간 초과가 뜬다.

하긴 이렇게 쉽게 풀리면 실버 문제가 아니지...

많은 분들이 추천하는 방법인 '에라토스테네스의 체'를 쓰지 않고서는 풀기 어려운 문제이다.

 

출처: 두산백과

2 이외의 모든 2의 배수를 지우고, 그 다음에는 3 이외의 모든 3의 배수를 지우면서 나아가는 방식이다.

해결과정

위와 같은 방법으로 2번째~9번째까지 시도했는데, 계속 틀렸다고 하더라.

비주얼스튜디오로 실행했을 때도 아무 문제 없었는데 백준은 역시 자비란 없다.

설상가상으로 배열요소가 1,000,000개를 지역변수에서 선언하니까 이건 vs에서도 에러가 떴다.(이건 전역변수로 선언함으로써 해결했다)

아직도 앞 코드가 왜 실패한건지 이유는 모르겠고, 어쩔 수 없이 다른 분의 코드를 참고했다(거의 동일하다고 봐야하나...감사합니다)

https://m.blog.naver.com/mjk270/221195689474

소수 구하기 (baekjoon 1929) - c 언어 "에라토스테네스 체"

코드

#include <stdio.h>

int arr[1000001];

int main() {
	int m, n;
	int i, j;
	scanf("%d %d", &m, &n);

	for (i = 2; i <= n; i++) {
		if (!arr[i]) {
			for (j = i + i; j <= n; j += i)
				arr[j] = 1;
		}
		if (i >= m && arr[i] == 0) printf("%d\n", i);
	}
	
	return 0;
}

결과

"10전11기"

덕분에 실5>실4로 승급했네요 굿