[Java] 프로그래머스 > 소수찾기

https://programmers.co.kr/learn/courses/30/lessons/12921

코딩테스트 연습 - 소수 찾기

 

문제 설명

• 1부터 입력받은 숫자 n 사이에 있는 소수의 개수 반환
• 소수는 1과 자기 자신으로만 나누어지는 수를 (1은 소수가 X)
• n은 2이상 1000000이하의 자연수입니다.

---

 

문제 보자마자 반복문으로 일차원적으로 풀었다.

그런데 시간 초과로 실패!

flag 변수 사용하면 더 간단했을텐데 .. 어쨌든 실패

 

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

 

다른 풀이 찾아보다가 발견한 방법

 

에라토스테네스의 체

수학자 에라토스테네스가 발견한 소수 찾는 방법, 소수의 배수들을 제외하며 소수를 찾는 알고리즘이다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

에라토스테네스의 체 (위키백과) 

class Solution {
  public int solution(int n) {
    int answer = 0;
    int[] numbers = new int[n+1];

    for(int i=2; i<=n; i++) numbers[i]=i;

      for(int i=2; i<n; i++) {

        if(numbers[i] == 0) continue;

        for(int j=2*i; j<=n; j+=i) numbers[j] = 0;
      }

      for(int i=0; i<numbers.length; i++) {

        if(numbers[i] != 0) answer++;
      }

    return answer;
  }
}

 

 

• n 크기 만큼 배열을 만들어 초기화시켜준다.
• 2부터 n까지의 배수를 0으로 만들고 0이 아닌 배열 값의 개수를 count한다.