소수 찾기

프로그래머스 코딩테스트

문제 설명

• 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
• 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
  (1은 소수가 아닙니다.)

제한조건

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

입출력 예

n	result
10	4
5	3

---

소수란?
약수가 1과 자기자신만 있는 1보다 큰 자연수 (2,3,5,7,... 등)

소수찾기 - 방법 1

• 2 ~ n-1 사이의 자연수로 n을 나누어, 나누어떨어지면 소수가 아님을 판별

나누어떨어진다는 것은 n의 약수라는 의미. 
즉, 1과 자기자신 외의 약수가 존재함으로 소수가 아니다.

// 소스코드(java)
public int solution1(int n){
	int answer = 0;
    boolean flag = true;
    for(int i = 2; i <= n; i++){
    	flag = true;
        for(int j = 2; j < i; j++){ // 약수 구하는 부분
			if(i%j == 0){
            	flag = false;
                break;
            }
		}
        if(flag) answer++;
    }
    return answer;
}

• 시간복잡도 : $O(n^2)$

소수찾기 - 방법 2

• 방법1의 약수 구하는 범위를 줄인 방법
• 범위는 자연수 n의 제곱근 까지
  • 자연수 n은 약수들의 곱셈으로 이루어져있다.
  • n의 제곱근을 기준으로 좌우는 약수들의 곱셈이 대칭을 이루고 있다.
    ex) 100 => 2x50, 4x25, 5x20, 10x10, 20x5, 25x4, 50x2
  • 그러므로 체크 범위를 제곱근 n까지로 줄일 수 있다.
    대칭구조에 의해
    • 있다면, 제곱근 n 이후에도 약수가 있고
    • 없다면, 제곱근 n 이후에도 약수가 없다.

// 소스코드(java)
public int solution2(int n){
	int answer = 0;
	boolean flag = true;
	for(int i = 2; i <= n; i++) {
		flag = true;
    	for(int j = 2; j <= Math.sqrt(i); j++) { // 제곱근까지 범위축소
	    	if(i%j == 0) {
	        	flag = false;
    	        break;
			}
		}
		if(flag) answer++;
	}
	return answer;
}

• 시간복잡도 : $O(n\sqrt{n})$

소수찾기 - 방법 3 (에라토스테네스의 체)

• 고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법.
  
  
• 알고리즘
  1. 1부터 n까지의 모든 자연수를 나열한다.
  2. 1부터 n까지의 수를 순회(i)하며 i의 배수를 모두 제거한다.
     • 1은 소수가 아니므로 제거
     • i는 제거하지 않는다. (i가 제거되지 않은 이유는 소수이기 때문)
  3. 더 이상 반복할 수 없을 때까지 2번 과정을 반복한다.
     
     
• 동작화면
  

public int solution3(int n) {
	int answer = 0;
	boolean[] prime = new boolean[n+1];
	for(int i = 2; i <= n; i++) {
		prime[i] = true;
	}
	for(int i = 2; i < Math.sqrt(n); i++) {
    	if(prime[i]) {
    		for(int j = 2; i*j <= n; j++) {
    			prime[i*j] = false;
    		}
    	}
    }
   	for(boolean val : prime) {
   		if(val)	answer++;
   	}
	return answer;
}

• 시간복잡도 : $O(n\log\log n)$