단계별로 풀어보기(기본 수학2 - 소수 구하기)

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

시간 초과

처음 보고 오 쉽겠네하고 제출했다가

 

시간 초과 걸린 문제

 

Scanner에서 BufferedReader으로 바꿔봤다가

 

다 해봤는데 안 돼서

 

for(int j = 2; j < i; j++) {
	    		
	if(i % j == 0) check = false;
	    		
}

이 부분을 좀 바꿔볼까 생각이 들었다.

 

for(int j = 2; j < i; j++) {
	    		
	if(i % j == 0){
		check = false;   
		break;
	}
	    		
}

break 추가해봤다.

 

입력 초과 떴다...

 

그래서 잘 생각해봤다.

 

문제의 입력 최댓값이 1,000,000였는데

 

대충 생각해보니 소수라면 어차피 전부 테스트해볼게 분명하니까

 

차라리 1부터 1,000,000까지

 

소인수 분해해서 나오는 가장 큰 소인수를 구하고

 

얘로 limit을 걸자고 생각했다.

 

전 문제 조금 수정해서

이클립스로 얘를 돌렸다.

 

한참 걸리고 max 값은 997였나? 그럴 거임.

 

그래서 이렇게 바꿨더니 성공했다.

 

위에 실패한 거는 j < i를

 

j < 998로 바꿨었는데 제출하자마자

 

아 저러면 i로 나누게 되니까 몫이 0 되고,

 

check = false 된다는 걸 깨달았다...