글 읽기 - 시간초과가 왜나오는걸까요?

kth004 6년 전 0

아무리 시간을 줄여보아도 시간초과가뜨네요. 왜이런지 알려주시면 감사하겠습니다. ㅠㅠ

#include<iostream>
#include<cstdio>

using namespace std;
#define n 1000000
int main()
{
	int input,i,j;
	int *arr;
	bool IsTrue = false;
	arr=new int[n];

	while(1){
		scanf("%d",&input);

		if(input==0){
			break;
		}

		for(i=3;i<=input;i+=2){
			arr[i]=i;
		}
//에라토네스의 체 사용. <- 이 부분에 서 문제일까요?
		for(i=3;i*i<=input;i+=2){
			if(arr[i]!=0){
				for(j=i+i;j<=input;j+=i){
					arr[j]=0;
				}
			}
		}

		for(i=3;i*2<=input;i+=2){
			if(((arr[i]+arr[input-i])==input) && arr[input-i]!=0 && arr[i]!=0 && arr[i]!=arr[input-i]){
				printf("%d = %d + %d\n",input,arr[i],arr[input-i]);
				IsTrue=true;
				break;
			}
		}

		if(IsTrue==false){
			printf("Goldbach's conjecture is wrong.\n");
		}
		IsTrue=false;
	}

	return 0;
}

h0ngjun7 6년 전 0

에라토스테네스의 채를 while 문 밖에서 한 번만 계산해보셔요.

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

문제

문제

출처

ICPC

시간초과가 왜나오는걸까요?

kth004 6년 전 0

h0ngjun7 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말