[백준/JAVA]1978번 소수 찾기

문제

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

주어진 수들 중에서 소수가 몇 개인지 개수만 세는 문제였다.

문제 풀이

1. 처음 생각한 풀이

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		StringTokenizer st=new StringTokenizer(br.readLine()," ");
        int result=0; //소수의 개수
        
        //약수 구하기
		for(int i=0;i<N;i++) {
			int count=0;
			int num=Integer.parseInt(st.nextToken());
			for(int j=1;j<=num;j++) {
				if(num%j==0) count++;
			}
			
            //약수가 2개라면(1이 제외된다.)
			if(count==2) { 
				result++;
			}
		}
		
		System.out.println(result);
	}
}

2. 시간복잡도를 고려한 풀이

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int N=Integer.parseInt(br.readLine());
		StringTokenizer st=w StringTokenizer(br.readLine(), " ");
		int result=0; //소수의 개수

		for(int i=0;i<N;i++) {
			int num=Integer.parseInt(st.nextToken());
			if(isPrime(num)) result++;
		}

		System.out.println(result);
	}

	public static boolean isPrime(int num) {
		if(num<2) return false;
		for(int i=2;i<=Math.sqrt(num);i++) {
			if (num%i==0) return false; //하나라도 나누어 떨어지면 소수 아님
		}
		return true;
	}
}