글 읽기 - 1929(소수구하기)

etkor4 2년 전 0

에라토스테네스의 체를 사용해서 소수로만 나누는걸 해봤는데요

아무래도 잘못생각한거같네요 계속 시간초과가 납니다

혼자 계속생각해봐도 루프가 증가만합니다 어떤방법으로 해결해야할까요?

#include <stdio.h>
int main(void){
	int m, n, j = 0, flag = 0, primeN[100000];
	primeN[0] = 2;
	scanf("%d%d", &m, &n);
	for(int i = 2; i <= n; i++){
		flag = 0;
		for(j = 0; primeN[j] != NULL; j++){
			if(i % primeN[j] == 0){
				flag = 1;
				break;
			}
		}
		if(flag == 0) primeN[j] = i;
	}
	for(int i = 0; primeN[i] <= n; i++){
		if(primeN[i] >= m && primeN[i] <= n) printf("%d\n", primeN[i]);
	}
	return 0;
}

dldyddlwl 2년 전 1

아래에 있습니다.

// 에라토스테네스의 체를 잘못 생각하고 계신 것 같습니다. 에라토스테네스의 체는 아래와 같은 과정을 거칩니다.

// 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
// 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
// 자기 자신을 제외한 2의 배수를 모두 지운다.
// 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
// 자기 자신을 제외한 3의 배수를 모두 지운다.
// 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
// 자기 자신을 제외한 5의 배수를 모두 지운다.
// 출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4


// 즉 쉽게 말하자면, 소수들의 배수들을 지워나가는 것입니다.
// 어떤 수의 배수가 되는 수는 그 정의에 의해서, 소수가 될 수 없기에 가능한 방법입니다.
// 그러면, 이 과정을 모두 거친 후에도, 지워지지 않은 숫자들은 소수라고 할 수 있는 것이죠!



// 예시 코드
const int MAX = 1000000;
bool check[MAX + 1];        // 전역변수로 선언하거나 0으로 초기화해서, 소수만 true로 만드는 방법!
check[0] = check[1] = true;
int N,M;

for (int i = 2; i <= M; i++) {
	if (check[i] == false) {    // 아직 지워지지 않은 수라면, 그 수의 배수들을 지워가자!            
		for (int j = i + i; j <= M; j += i) {    // j는 i+i, 즉 2*i (i의 2배부터 시작, 그리고 3배, 4배 5배 ...)
			check[j] = true;                    // 배수들은 true로 만들어 버리기!! 이런식으로 M까지 진행     
		}
	}
}

// 모든 과정을 끝낸 후, false인 친구들만 출력하면 끝!

etkor4 2년 전 0

@dldydwl

너무 큰가르침이었습니다

나눠서 지우는 것이 배수를 지우는 것이라 같은 것이라 생각했었는데

나눌 때는 매번 작은수로돌아가야되니 반복 횟수 차이가 엄청나네요

거기다 배열을 소수를 넣는 용도로만 생각했는데 이렇게도 쓸 수 있네요 감사합니다

처음에 bool말고 int배열로 선언하니 터져버리더군요 bool도 잘 쓸 수 있게 됐습니다

정말 감사드려요

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1929(소수구하기)_C언어 시간초과

etkor4 2년 전 0

dldyddlwl 2년 전 1

etkor4 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말