소수 찾기/java/프로그래머스/Level1

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

코딩테스트 연습 - 소수 찾기 | 프로그래머스

<소수 찾기>

 

○ 풀이

public class Sosu {
 
    public static void main(String[] args) {
        
        int n = 10;
        int count = 0;
        // boolean배열로 1부터 n사이의 모든 수를 표현하기
        boolean[] a = new boolean[n+1];
 
        // a[]배열 안의 2부터 n까지의 값을 true로 넣어주기
        for(int i=2;i<n+1;i++) {
            a[i] = true;
        }
        // 여기까지 1을 제외한 모든 수는 true가 들어가 있음
        // 1은 소수가 아니므로 초기값은 2로 설정
 
        // 루트 처리
        int to = (int)Math.sqrt(n+1);
        // 변수 to는 숫자 n을 루트로 처리하여 int로 형변환 한 값이다.
        // 따라서 나머지가 없어지고 정수값만 남는다.
        // ex) 루트10 는 3이 된다.
        
        // 2부터 정수로 바뀐 수 까지 반복한다
        for(int i=2;i<=to;i++) {
            if(a[i]==true) {            // true일 경우 check한다
                for(int j=i;j*i<=n;j++) {    // j는 i부터 1씩 증가하여 i의 배수를 골라내는 변수
                    a[i*j] = false;
                }
            }
        }
 
        // true값만 출력하기!
        for(int i=2;i<=n;i++) {
            if(a[i])        // a[i]가 true일 경우 count한다
                count++;
        }
        System.out.println(count);
    }

 

- 에라토스테네스의 체를 이용하여 소수를 찾아낸다

- 어떤 수의 배수는 소수가 될 수 없기 때문에 배수들을 모두 걸러내는 방식으로 처리한다.

- boolean 배열을 선언하여 1을 제외한 배열내의 모든 수를 true값으로 넣어준다. 

- 1은 소수가 아니기 때문에 초기값을 2로 주어 번지수가 아닌 배열의 인덱스값으로 소수를 판별하기로 한다.

- 숫자 n이 주어졌을때 n에 루트처리를 하게 되면 정수 처리된 수의 배수들까지만 체크하면 된다.

  ex. 루트 10은 3의 배수까지만 존재한다. 루트 30은 5의 배수까지만 존재한다...

- 24번 Line ~ 30번 Line : 배수들을 골라내어 false처리해주기

- true일 경우에만 출력하기