글 읽기 - 4948번 시간초과 질문

im0121 4년 전 0

여러가지 방법 해봤으나.. 자꾸 시간 초과가 떠서 질문합니다.

처음 한 방법이 1 ~ N 까지 전부 나눠서 CNT == 2 일때 소수인지를 판별하도록 했었는데

시간초과가 떠서 해결 방법을 찾다 제곱근 까지만 하면 해결 및 시간단축을 할 수 있다는걸 보고 했는데

다시 시간 초과가 뜨네요 ㅠ 이 방법 말고 무슨 다른 방법 하나가 더 있는건 봤는데 이 방법으로 시간초과가 안날 수 없게 할 수 있을까 해서 여쭙니다.

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

int main(){
	
	int num,i,k,j,cnt,ans=0;

	
	double x;
	
	i=0;
	
	
	while(1){
		
		scanf("%d",&num);
		
		if(num == 0){
			break;
		}
		
		ans = 0;
		
		for(k=num+1;k<=2*num;k++){
			
			cnt = 0;
			x = sqrt(k);
			
			for(j=1;j<=x;j++){
				
				if(k%j == 0){
					
					cnt = cnt + 1;
					
				}
			}
			if(cnt==1){
				
				ans = ans + 1;
				
			}
			
		}
		if(ans != 0){
			printf("%d\n",ans);
		}
	}
} 

wogus23 4년 전 2

에라토스테네스의 체를 활용하시면 시간초과 해결 하실거에요

im0121 4년 전 0

해결했습니다~!!

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

문제

문제

출처

ICPC

4948번 시간초과 질문

im0121 4년 전 0

wogus23 4년 전 2

im0121 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말