[백준] - 소수 찾기 (1978) (자바/Java)

 

 

 

 

 

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

 

 

 

 

 

문제.

---

 

 

 

 

 

 

 

 

풀이.

---

 

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int count = 0; //약수 개수 카운트
        int num = sc.nextInt();

        for (int i = 0; i < num; i++) {

            boolean chk = true;
            int n = sc.nextInt();

            if (n == 1) { //1일 경우 반복문으로 패스
                continue;
            }

            for (int j = 2; j <= Math.sqrt(n); j++) {
                if (n % j == 0) {
                    chk = false;
                    break;
                }
            }
            if (chk){
                count++;
            }

        }
        System.out.println(count);


    }

}

 

이번 문제는 소수 찾기다.

소수는 자기 자신과 1만을 약수로 가지는 자연수를 의미한다. 

우선 풀이 식 설명을 해보겠다.

 

1. 약수 개수 카운트를 해주는 변수를 만들어준다. int count;

2. 소수인 경우 true, 소수가 아닌 경우 false로  boolean 값을 만들어 준다. 

3. 두번째 for문에서 Math.sqrt(); 함수를 사용해 n 입력값 (제곱근) 만큼 반복한다. 

4. n % j 가 0 이 나올 경우 boolean 값은 false 바꿔준다 왜냐? 자기 자신을 제외한 수가 있기 때문에 소수가 될 수 없다.

5. 4번의 조건식이 충족 하지 않을 경우 소수 이므로 count 값을 1씩 증가시켜준다.