백준/1978/소수 찾기/JAVA

1978번: 소수 찾기 (acmicpc.net)

1978번: 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int testcase  = sc.nextInt();
        int cnt = 0;
        for(int i=0; i<testcase;i++){ //testcase만큼 반복
            int k = sc.nextInt();
            boolean isPrime = true;
            
            if( k ==1)
                continue; 
            for(int j=2;j<=Math.sqrt(k);j++){
                if(k % j ==0){
                    isPrime = false;
                }
            }
            if(isPrime){
                cnt++;
            }
        }
        System.out.println(cnt);
    }
}

 

제곱근을 이용하기위해 Math.sqrt(k) 를 이용하였다. k의 제곱근 이하 숫자의 어떤 수로도 나눠지지않으면 소수가 되는 것이다. 예를 들어 25의 제곱근은 5이기 때문에 5는 소수가 아니다. 근데 29의 제곱근은 5.xxx이고 1,2,3,4,5로 나눠도 나누어 떨어지지 않기 때문에 소수가 된다. 그리고 1은 예외이기 때문에 if문을통해 예외처리를 해주어야한다.