강의로 돌아가기
박정현

수행 시간 초과

class Solution{

public int solution(int n){
int answer = 0; int i = 2;
while(i <= n){
int j = 2;
while(j <= i){
if(j < i && i % j == 0){
break;
} else if(i % j == 0){
answer++;
break;
} j++;
} i++;
} return answer;
}
}

for문에서 일부러 while문으로 바꿔서 해봤는데도 마지막 테스트 3문제에서 수행시간초과로 통과를 못하네요 ㅜ 어떻게 해야할까요??

  • 이승우
    저도 똑같네요..
    이승우―2018.06.12 09:37
  • -
    에라토스테네스의 체 검색 키워드
    -―2018.07.13 17:32
  • paul-kim
    저는 기존에 나와있는 소수의 개수를 구하는 공식보다, 최대한 test 하는 대상을 줄이고 효율적인 연산(double 보단 int 형 연산)을 쓰니까 pass 되었어요
    paul-kim―2018.07.23 01:25
1 개의 답변

최적화를 하셔야합니다.
소수를 구할때 n보다 작은 수들을 전부다 나눠보는것에서 n의 루트까지만 나누어서 떨어지는지 체크만 하셔도됩니다. 만약 n의 루트까지도 안나눠지면 소수로 판단할 수 있습니다.

두번째로 n보다 작은 소수들로 나누어 지지 않으면 소수로 판단할 수 도 있습니다.
저도 이 두가지 방법을 추가하니깐 효율성에서 통과하더라구요

  • chloe
    n의 루트까지만 나누어서 떨어지도록 구현하면 test11 만 통과하지 못하더라구요. 두 번째 방법(n보다 작은 소수들로 나누어지지 않으면 소수로 판단)이 어떻게 효율성을 높이는건가요?
    chloe―2018.07.04 19:11
  • 6까지의 소수를 구할 때 2부터 5까지 나눠보지 말고 2, 3, 5만 나눠도 됩니다. 소수가 아닌 숫자들은 그보다 작은 소수들 중 하나에 항상 나누어 떨어지니깐요.
    탈퇴한 사용자―2018.07.05 15:49
답변 쓰기
이 입력폼은 마크다운 문법을 지원합니다. 마크다운 가이드 를 참고하세요.