[알고리즘/Programmers] LV1. 소수 찾기

Programmers LV1. 소수 찾기

문제 설명

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

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

 

제한 사항

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

 

입출력 예

n	result
10	4
5	3

 

사용 언어

Java

 

해결 방법

1. 2~j 이하까지 n이 j로 나눠지는지 판별 -> 시간 초과

2. 2~Math.sqrt(j) 이하까지 n이 j로 나눠지는지 판별 -> 2부터 진행하면 for문 sqrt 조건에 안걸려서 실패.

3. 에라토스테네스의 체로 판별 -> 통과

  : n+1개의 원소를 갖는 배열을 하나 두고 2(i)부터 n까지 i의 배수를 배열에 체킹한다. 체킹되어있지 않은 배열 인덱스를 카운트하여 판별한다.

 

코드

public class test_12921 {
    public static void main(String[] args) {
        solution(30); // 4
    }
    static public int solution(int n) {
        int answer = 0;

        // n+1 false로 채운 배열을 생성.
        boolean[] checked = new boolean[n+1];

        // 2부터 n까지 늘리면서 각 숫자의 배수를 배열에 true로 채운다.
        for(int i=2; i<=n; i++) {
            if(!checked[i]) answer++; // checked 되지 않은 배열 카운트++
            for(int j=i; j<=n; j+=i) {
                if(checked[j] == true) continue;
                checked[j] = true;
            }
        }

        return answer;
    }
}

 

참고

javacoding.tistory.com/133

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

 

---

 

지난 번에 비슷한 소수 문제를 풀었었고 다시 복기 했는데도 스스로 못푼 문제이다.

Math.sqrt() 를 쓰려면 2부터 돌리면 for문 조건에 걸리지 않는다. 이 방법을 쓰려면 for문 내부에 조건을 추가로 주어야할 것 같다.

사실 '에라토스테네스의 체' 방법은 지난번에 제대로 숙지 못하였다. (이름도 어려워.. 아리스토텔레스인줄 ㅠ)

이제 구조를 숙지하였으니 다음에 이런 문제 나와도 당황하지 않고 풀어야겠다 ....!