소수 찾기

프로그래머스 1단계 Java 소수 찾기 문제입니다.

---

문제 설명

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

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

 

제한 조건

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

입출력 예

n	result
10	4
5	3

 

입출력 예 설명

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

입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

 

문제 해결 방법

① 에라토스테네스의 체 기법을 이용

② 소수의 배수 확인용 배열을 크기 n + 1만큼 생성 (default 값 ▶ false)

③ 소수 2부터 √n까지 소수의 배수 확인

    ⑴ 소수의 배수 ▶ 배열의 해당 인덱스를 true로 설정

    ⑵ 배수가 아닌 경우 ▶ 소수이므로 배수에 해당하는 값들의 인덱스를 true로 설정

④ 인덱스의 값이 false인 인덱스는 소수이므로 개수에 포함하여 반환

---

class Solution {
    public int solution(int n) {
        int answer = 0;
        // ② 소수의 배수 확인용 배열을 크기 n + 1만큼 생성 (default 값 ▶ false)
        boolean chkPrime[] = new boolean[n + 1];
        
        if(n < 2) {
        	return 0;
        }
        else {
        	chkPrime[0] = chkPrime[1] = true;
        }
        
        // ③ 소수 2부터 √n까지 소수의 배수 확인
        for(int i = 2; i <= Math.sqrt(n); i++) {
            // ⑴ 소수의 배수 ▶ 다음 수로 계속
            if(chkPrime[i] == true) {
        		continue;
        	}
        	// ⑵ 배수가 아닌 경우 ▶ 소수이므로 배수에 해당하는 값들의 인덱스를 true로 설정
        	for(int j = i * i; j < chkPrime.length; j+=i) {
        		chkPrime[j] = true;
        	}
        }
        // ④ 인덱스의 값이 false인 인덱스는 소수이므로 개수에 포함하여 반환
        for(boolean cnt : chkPrime) {
        	if(!cnt) {
        		answer += 1;
        	}
        }
        
        return answer;
    }
}

---

 

※ 에라토스테네스의 체

고대 그리스의 수학자 에라토스테네스가 발견한 소수를 찾는 방법입니다.

이해하기 어려분 부분이 있다면 아래의 링크를 통하여, 어떤 과정을 통해 소수가 아닌 수를 제거하는지 가시적으로 확인하실 수 있습니다.

Java뿐만 아니라 C++, python 등 여러 프로그래밍 언어로도 구현이 되어있어 참고하시면 좋을 것 같습니다.

 

에라토스테네스의 체 ▶ https://ko.wikipedia.org/wiki/에라토스테네스의_체

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

 

※ 위 코드는 해결 방법 중 한가지이며 더 효율적인 코드가 있을 수 있습니다.

 

문제 풀어보기 ▶ https://programmers.co.kr/learn/courses/30/lessons/12921?language=java

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