Programmers / Level 1 / 소수 찾기

[문제설명]

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

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

[제한사항]

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

[입출력 예]

n	result
10	4
5	3

 

import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;

        for(int i=2; i<=n; i++) { 
            boolean flag = true;

            for (int j = 2; j <= Math.sqrt(i); j++) {
                if(i%j == 0) { 
                    flag = false;
                    break;
                }
            }
            if(flag==true) answer++;
        }
        System.out.println(answer);

        return answer;
    }
}

처음엔 for문을 j < i 까지로 설정했는데, 시간 초과가 떠서

a가 b로 나눠 떨어진다면 그 때의 몫은 반드시 a의 제곱근보다 작기 때문에 Math.sqrt(i)로 바꿔주었다.

 

다른 풀이방법도 있나 찾아봤는데, "에라토스테네스의 체"를 이용한 방법이 꽤 보였다.

 

에라토스테네스의 체

에라토스테네스의 체는 소수를 찾는 방법이다.

 

알고리즘1. 2부터 소수를 구하고자 하는 모든 구간의 수 나열

2. 2는 소수임

3. 자기 자신을 제외한 2의 배수 지우기

4. 남아있는 수 중 3은 소수임

5. 자기 자신 제외한 3의 배수 지우기

6. 남아있는 수 중 5는 소수

7. 자기 자신 제외한 5의 배수 지우기

8. 남아있는 수 중 7은 소수

9. 자기 자신 제외한 7의 배수 지우기

10. 위 과정 반복하면 구하는 구간의 모든 소수가 남게됨

 

즉, 2/3/5/7은 소수이고 n까지의 2,3,5,7의 배수를 모두 지우면 된다!

import java.util.*;

class Solution {
    public int solution(int n) {
        int answer = 0;

        int[] arr = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            arr[i] = i;
        }

        // 2부터 시작해서 그의 배수들을 0으로 만들기
        for (int i = 2; i <= n; i++) {
            for (int j = 2 * i; j <= n; j+=i) {
                if(j<=n) {
                    arr[j] = 0;
                }
            }
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != 0) {
                answer++;
            }
        }

        return answer;
    }
}

우선, arr배열을 만들고, 2부터 n까지의 숫자를 넣어준다 (1은 소수가 아니므로 제외)

arr배열을 돌며, 2부터 시작해 2,3,...의 배수들은 0으로 만들어준다.

단, 2,3,5,7은 소수이므로 이는 제외해야 하기 때문에 for문을 j=2*i부터 시작한다.(4,8,... / 6,9..)

 

그렇게 하면 소수가 아닌 수들은 배열의 값이 0이 된다.

for문을 다시 돌며 배열의 값이 0이 아닌 값들인 경우 answer++를 해줘서 소수의 개수를 알아낸다.