AlgorithmProgrammers

프로그래머스 소수

, ,

1. 문제 링크

프로그래머스 소수

2. 문제 조건

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

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

제한 조건
n은 2이상 1000000이하의 자연수입니다.

3. 컴퓨팅 사고

  • 에라토스테네스의 체를 사용합니다.
  • 일반 소수처럼 구현하게 되면 효율성에서 통과를 하지 못합니다.

에라토스테네스의 체 원리
1부터 N까지의 모든 소수를 구하려면 에라토스테네스의 체를 사용한다

1.2부터 N까지 모든 수를 써놓는다
2.아직지워지지 않은수중에서 가장 작은값을 찾는다
3. 해당 소수 값은 소수가 된다.
4. 이제 그수의 배수를 모두 지운다.

해당원리를 가지고 에라토스 테네스의 체를 구현하게된다면 쉽게 구할수 있습니다.

에라토스테네스의 체를 쓰면서 두가지 경우를 실험하였는데, 하나의 경우는 효율성에서 통과를 하지 못하였고, 하나는 통과를 하였습니다. 그 이유가 있었는데 내부 for문에서 N의 크기에 따라 ii를 할지 i2, i+i의 값에 따라 효율성이 달라지게 됩니다. 그 이유는 i가 100만일 경우 i*i는 100만을 넘어가기 때문입니다.

4. 소스 코드

효율성 실패

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class 소수찾기 {
    static boolean[] check = new boolean[1000001];
    public static void main(String[] args) {

        int n =10;

        check[0] = true;
        check[1] = true;

        for(int i=2; i<=n; i++){
            if(!check[i]){
                for(int j=i*i; j<=n; j+=i){
                    check[j] = true;
                }
            }
        }

        int sum = 0;
        for(int i=2; i<=n; i++){
            if(!check[i]){
                sum++;
            }
        }

        System.out.println(sum);


    }
}

효율성 통과

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class 소수찾기 {
    static boolean[] check = new boolean[1000001];
    public static void main(String[] args) {

        int n =10;

        check[0] = true;
        check[1] = true;

        for(int i=2; i*i<=n; i++){
            if(!check[i]){
                for(int j=i+i; j<=n;j+=i){
                    check[j] = true;
                }
            }
        }

        int sum = 0;
        for(int i=2; i<=n; i++){
            if(!check[i]){
                sum++;
            }
        }

        System.out.println(sum);


    }
}


Share