소수 찾기

Programmers.co.kr 코딩테스트 연습

Level 1 - 사용언어 Java - 소수(Prime number) 찾기

나의 답안 - 첫번째 시도, 응답시간 초과

public class IsPrime {

  public int solution(int n) {
    int answer = 0;
    for (int i = 2; i <= n; i++) {
      boolean isPrime = true;
      for (int j = 2; j <= i - 1; j++) {
        if (i % j == 0) {
          isPrime = false;
          break;
        }
      }
      if (isPrime)
        answer++;
    }

    return answer;
  }
}

효율성을 높이기 위한 두번째 시도, 이 역시 응답시간 초과

public class IsPrime {
public int solution2(int n) {
    int answer = 0;
    for (int i = 2; i <= n; i++) {
      boolean isPrime = true;
      for (int j = 2; j <= i / 2; ++j) {
        if (i % j == 0) {
          isPrime = false;
          break;
        }
      }
      if (isPrime)
        answer++;
    }

    return answer;
  }
}

처절한 세번째 시도, 이 역시 응답시간 초과

public class IsPrime {
public int solution3(int n) {
    if(n < 8) {
      switch (n) {
      case 2 :
        return 1;
      case 3 :
      case 4 :
        return 2;
      case 5 :
      case 6 :
        return 3;
      case 7 :
        return 4;
      }
    }
    
    int answer = 4;
    for (int i = 8; i <= n; i++) {
      boolean isPrime = true;
      
      for (int j = 2; j*j <= i / 2; ++j) {
        if(i <= 120) {
          if (i % 2 == 0 ||
              i % 3 == 0 ||
              i % 5 == 0 ||
              i % 7 == 0) {
            isPrime = false;
            break;
          }
        } else {
          if (i % 2 == 0 ||
              i % 3 == 0 ||
              i % 5 == 0 ||
              i % 7 == 0 ||
              i % 11 == 0 ||
              i % 13 == 0) {
            isPrime = false;
            break;
          }
        }
        
        if (i % j == 0) {
          isPrime = false;
          break;
        }
      }
      if (isPrime)
        answer++;
    }

    return answer;
  }
}

검색해서 찾은 답안. 수학적 조건을 맞추지 못하면 효율성 테스트까지 가기도 전에 응답시간 초과로 실패하도록 되어 있다. 결국엔 답은 하나??

public class IsPrime {
public int solution4(int n) {
            int answer = 0;
            
            int[] number = new int[n+1];
            
            //2부터 n까지의 수를 배열에 넣는다.
            for(int i=2; i<=n; i++) {
                number[i] = i;
            }
            
            //2부터 시작해서 그의 배수들을 0으로 만든다.
            //후에 0이면 넘어가고 아니면 그의 배수들을 다시 0으로 만든다.
            for(int i=2; i<=n; i++) {
                if(number[i]==0) continue;
                
                for(int j= 2*i; j<=n; j += i) {
                    number[j] = 0;
                }
            }
            
            //배열에서 0이 아닌 것들의 개수를 세준다.
            for(int i=0; i<number.length; i++) {
                if(number[i]!=0) {
                    answer++;
                }
            }
            
            return answer;
        }
}