글 읽기 - (C)다른 풀이보다 제 풀이가 오래 걸리는 이유를 모르겠습니다.

ehdghks709 5년 전 0

원래는 다른 방식으로 풀었는데,

ove16님의 코드를 참조해 에라토스테네스의 체를 구현했습니다.

ove16님은 1 ≤x ≤1000000의 범위에서 에라토스테네스의 체를 구현하셨고,

저는 입력값이 a, b라 할 때 a ≤x ≤b의 범위에서 에라토스테네스의 체를 구현했습니다.

이러면 일반적인 경우에 제 코드가 더 빠르고,

a=1, b=1000000의 경우에도 두 코드의 속도가 거의 비슷해야 한다고 생각했습니다.

그런데 저는 시간이 44ms고, ove16님은 20ms네요..

왜 이런 건가요?

//제 코드
#include <stdio.h>
#include <math.h>
int a, b, i, prime[1000000], sqrtnum, k,j;
int main(void)
{
	prime[0] = -1;
	scanf("%d %d", &a, &b);
	for (i = 2;; i++)
	{
		if (prime[i-1] == -1)
			continue;
		else if (i > b)
			break;
		k = a / i;
		if (k <= 1)
			k = 2;
		while (i*k <= b)
		{
			prime[i*k - 1] = -1;
			k++;
		}
	}
	for (i = a-1; i <= b-1; i++)
		if (prime[i] != -1)
			printf("%d\n", i + 1);
	return 0;
}

//9964384번 ove16님 코드
#include <stdio.h>

int prime[1000001];

int main() {
	int M;
	int N;
	scanf("%d", &M);
	scanf("%d", &N);

	//prime[1] = 숫자 1 의미 
	for (int i = 2; i < 1000001; i++) {
		if (prime[i] == -1) {
			continue;
		}
		int primeNum = i;
	/*	while (j) {
			if (i%j-- == 0) {
				cnt++;
				if (cnt > 2) {
					break;
				}
			}
		}*/
	
		
		//소수 입니다. 
		//printf("소수입니다 : %d\n", i);
		prime[i] = 1;

		//에라토스테네스의 체를 이용하여 배수를 모두 -1로 변경
		int k = 2;
		int chk = i * k;
		while (chk<1000001) {
			prime[chk] = -1;
			k++;
			chk = i * k;
		}
			
		
		
	}
	for (int i = M; i <= N; i++) {
		if (prime[i] == 1) {
			printf("%d\n", i);
		}
	}

	return 0;

}

jupiterbjy 5년 전 0

2시간 가까이 이런저런 테스트해본 결과 비주얼 스튜디오 상에선 1번코드가 1~1,000,000 외에는 항상 더 빨랐습니다. 왜 더 시간이 걸린건지 모르겠군요.. 나눗셈이 곱셈보다 6배 느리다는 얘기도 있지만, 채점 CPU가 제온 E5라 해당사항은 없을것 같고..

한번 다시 제출해보시라는 말밖에 해드릴수가 없군요..

ove16 3년 전 0

으음...
저는 잘 모르겠습니당 ㅠ
다시 제출해봤는데 20ms 로 똑같네요

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

문제

문제

출처

ICPC

(C)다른 풀이보다 제 풀이가 오래 걸리는 이유를 모르겠습니다.

ehdghks709 5년 전 0

jupiterbjy 5년 전 0

ove16 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말