[백준/JAVA] 1978 : 소수 찾기 ( 기본 수학 2 )

문제

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

입력

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

출력

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

 

예제입력	예제출력
4 1 3 5 7	3

 

⭕ 풀이

 

import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args)throws IOException{
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int count = 0;
        while(st.hasMoreTokens()){
            
            int num = Integer.parseInt(st.nextToken());
            int devideNum = 0;
            for(int i=1;i<=num;i++){
                if(num%i==0){
                    devideNum++;
                    if(devideNum>2){break;}
                }
            }
            if(devideNum==2){
                count++;
            }
        }
        System.out.println(count);
    }
}

✅ 생각의 흐름

소수는 1보다 큰 자연수 중 1과 자기자신만을 약수로 가지는 수로 정의된다.

즉, 1은 소수가아니며 소수는 1을 포함해 총 약수가 2개라는것이다.

 

그럼 해당 숫자를 for문으로 i를 1부터 1씩 증가하며

나눠본뒤 해당 숫자를 i로 나눈 나머지가 0이되는 즉 약수를 세어 2라면 해당숫자는 소수란얘기가 된다.

그리고 i를 증가시키며 약수를 세던중 2보다 커진다면 소수가 아니라는 소리니까 break로 탈출한다.

그렇게 for문이 끝났으면 약수가 2인지 확인하고 다음 수를 받아서 진행한다.

 

 

 

 

-출처

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