글 읽기 - 시간초과입니다...

y718j 8달 전 0

이렇게 코드를 작성해봤습니다. 답은 제대로 나옵니다. 하지만 채점을 하면 계속해서 시간초과가 나옵니다. 어느 부분이 고쳐져야 되는지 아니면 틀렸는지 알려주시면 감사하겠습니다!

#include <stdio.h>
#include <math.h>

int main(){
	int arr[300000];
	int num,dbnum;
	int check;
	
	while(1){
		check=0;
		scanf("%d",&num);
		
		if(num==0)
			break;
		
		dbnum=2*num;
		
		for(int i=num+1; i<=dbnum; i++)
			arr[i]=i;//배열에 2n까지 숫자 집어넣기
		
		for(int i=num+1; i<=dbnum; i++){
			
			if(num==1)
				break;
			
			if(i>dbnum)
				break;
			
			for(int k=2; k<i; k++){
				if(arr[i]%k==0){
					arr[i]=-1;
					break;
				}
			}
		}
		
		for(int i=num+1; i<=dbnum; i++){
			if(arr[i]>0)
				check++;	
		}

		if(num==1)
			printf("1\n");
		else
			printf("%d\n",check);
	}
}

shg9411 8달 전 0

에라토스테네스의 체 검색해보세요!

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

문제

문제

출처

ICPC

시간초과입니다...

y718j 8달 전 0

shg9411 8달 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말