[프로그래머스 / Level1] 소수 찾기 (Java)

문제

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

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

*소수 : 자신과 1 이외의 정수로 나누어떨어지지 않는 정수. (1은 소수가 아님)
= 2~n-1까지 어떤 정수로도 딱 나누어 떨어지지 않음 (n % 2 != 0) ~ (n % n-1 != 0)

 

기존 코드 (효율성 실패)

class Solution {
    public int solution(int n) {
        int answer = 0;
        
        for(int i = 2; i <= n; i++){
            int j;
            for(j = 2; j < i; j++){
                if(i % j == 0){
                    break;                  //for문 도중에 나누어 떨어지는 수 발견
                }
            }
            if(j == i){
                answer++;                   //for문 끝까지 나누어 떨어지는 수 발견안됨
            }
        }
        
        return answer;
    }
}

- 2~n의 수를 차례대로 2부터 해당 수 사이의 값으로 나누어 떨어지는지 반복해서 체크.
- 그러나 불필요한 판단 과정(반복)이 수행되어 효율성에서 시간초과.

• n이 소수인 경우 : for문이 끝까지 실행됨. → i는 계속 증가해서 i == n
• n이 소수가 아닌 경우 : for문이 중단됨(break). → i가 n이 되기전에 반복문을 탈출해서 i < n

 

개선 코드1 (효율성 실패)

class Solution {
    public int solution(int n) {
        int answer = 0;
        int idx = 0;
        int[] prime = new int[500];
        
        prime[idx++] = 2;                   //2는 첫번째 소수
        answer++;
        
        for(int i = 3; i <= n; i+=2){       //짝수는 제외 
            int j;
            for(j = 1; j < idx; j++){       //i는 홀수이므로 prime[0] 2로는 비교할 필요X
                if(i % prime[j] == 0){
                    break;
                }
            }
            if(j == idx){
                prime[idx++] = i;
                answer++;
            }
        }
        
        return answer;
    }
}

- n이 2 또는 3으로 나누어떨어지지 않으면 2*2(4), 2*3(6)으로도 나누어떨어지지 않는다.
- 홀수만을 소수 판단 대상으로 지정, i보다 작은 소수들(prime배열)로 나누어떨어지는 체크하는 걸로 소수 판단.
- 첫번째 for문 대상은 3이상 홀수만, 두번째 for문 대상은 그 이전에 나온 소수들로 제한했음에도 효율성에서 시간초과.

• 짝수는 모두 2로 나누어떨어지기 때문에(짝수 전제조건 : n % 2 ==0), 짝수 중에서는 2가 유일한 소수
• 소수 n은 2부터 n-1까지의 어떤 소수로도 나누어떨어지지 않는다.

 

개선 코드 2 (성공)

class Solution {
    public int solution(int n) {
        if(n == 2) { return 1; }         //연산 대상으로 홀수만 사용할것이기 때문에 유일한 짝수 소수인 2는 미리거르기
        
        int answer = 0;
        int idx = 0;
        int[] prime = new int[1000000];
        
        prime[idx++] = 2;
        prime[idx++] = 3;
        answer+=2;
        
        for(int i = 5; i <= n; i+=2){                       //홀수만
            boolean isPrime = true;
            for(int j = 1; prime[j] * prime[j] <= i; j++){  //제곱근 이하 소수만
                if(i % prime[j] == 0){
                    isPrime = false;
                    break;
                }
            }
            if(isPrime){
                prime[idx++] = i;
                answer++;
            }
        }
        
        return answer;
    }
}

- 첫번째 for문의 대상은 5이상 홀수만 (i가 3일 경우 prime배열 길이가 1일때, prime[1] * prime[1] <= i 조건이 수행되어버리기 때문에 index가 넘어가버림), 두번째 for문의 대상은 i의 제곱근 보다 작은 소수들로 제한.
- "j는 i의 제곱근 보다 작아야한다."는 "j의 제곱은 i보다 작아야 한다."로 대체 가능.
  *제곱근을 구하는 메서드는 Math.sqrt()
- 드디어 정확성, 효율성 테스트 통과....

• 소수n은 n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다.

 

에라토스테네스의 체

고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법에 대한 알고리즘

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. (2~n)
2. 2는 소수이므로 소수배열(prime)에 2를 추가한다.
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
   (※ 2의 배수라는 건 즉, 2로 나누어떨어지는 수라는 거니까 절대 소수가 아님)
4. 남아있는 수 가운데 3은 소수이므로 소수배열에 3을 추가한다.
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 소수배열에 5를 추가한다.
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 소수배열에 7을 추가한다.
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남게된다.

 

public int Eratos(int n) {
	int cnt = 0;
	ArrayList<Boolean> primeList = new ArrayList<Boolean>(n+1);
	
	//0번째와 1번째는 소수 아님
	primeList.add(false);		
	primeList.add(false);
	
	//2~n까지 소수로 설정
	for(int i=2; i<=n; i++) {
		primeList.add(i, true);
	}
	
	//2부터 n의 제곱근보다 작을 때까지, 각각의 배수들을 지운다.
	for(int i=2; (i*i) <= n; i++) {
		if(primeList.get(i)) {
			for(int j = i*i; j <= n; j += i) {	//i*i 미만은 이미 이전 i의 반복에서 처리되었으므로 j의 시작값은 i*i로 최적화 가능
				primeList.set(j, false);		//i의 배수는 소수 아님
			}
		}
	}
	
	for(int i=0; i<=n; i++) {
		if(primeList.get(i) == true) {
			cnt++;
		}
	}
	
	return cnt;
}

- 0~n까지 각 정수의 소수여부(true/false)를 저장할 Boolean타입의 ArrayList를 선언
- 2부터 n의 제곱근까지 범위에서 각 정수의 배수를 소수가 아님으로 처리한다. 해당 처리를 반복하다 소수들만 true인 채로 남게된다.
- i의 배수는 소수가 아님으로 처리하는 과정에서 i*i 미만은 이미 이전 i의 반복에서 처리되었으므로 j의 시작값은 i*i로 최적화할 수 있다. (ex: 3*2는 2*3에서 처리되었고, 5*3은 3*5에서 이미 처리됨)

 

---

[참고자료]

• 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/12921
• 자료구조와 함께 배우는 알고리즘 입문(Java편)
• 에라토스테네스의 체, 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