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

💁‍♀️ 링크

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

 

📃 문제 

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)

 

제한 조건

• n은 2이상 1000000이하의 자연수입니다.

입출력 예 #1

• 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환

 

🐾 문제풀이

에라토스테네스의 체 알고리즘을 이용하여 소수를 찾는다.

 

🔗 참고사이트(위키백과)  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

 

1. 소수를 판별할 범위만큼의 배열을 생성하여 초기화한다.

   (최종적으로 소수이면 true, 아니면 false의 값을 가지게 된다.) 

2. 0과 1은 소수가 아니므로 false로 처리한다.

3. 2부터 시작해서 2,3,4 ... 등 특정 수의 배수에 해당하는 수를 모두 false로 변경한다.

 

💻 코드

import java.util.ArrayList;
class Solution {
	//
    // 효율성 테스트 미통과
    //
    public int solution(int n) {
        int answer = 0;
        ArrayList<Boolean> primeList = new ArrayList<>(n+1);
        primeList.add(false);
        primeList.add(false);
        
        for(int i=2; i<=n; i++){ primeList.add(i,true); }
        for(int i=2; i*i<=n; i++){
            if(primeList.get(i)){
                for(int j= i*i; j<=n; j+=i){ primeList.set(j, false); }
            }
        }
        for(Boolean prime : primeList){
            if(prime) answer++;
        }
        return answer;
    }
}