백준 1978 ( 소수 찾기)

문제

---

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

 

 

 

 

풀이

---

문제 자체는 소수를 찾는 다는 문제라 쉽지만.. 알고리즘을 기록해두기 위해 풀었다.

 

소수를 찾는 방법은 세가지다.

1.  반복문을 통해 2 부터 (N-1) 까지 약수가 없으면 소수
2.  반복문을 통해 2 부터 (N/2) 까지 약수가 없으면 소수
3.  반복문을 통해 2 부터 N 제곱근까지 약수가 없으면 소수

이 중에서 3번의 방식이 시간복잡도가 가장 짧아서 3번으로 문제를 풀었다.

 

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class Main {	
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) throws IOException{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		//Scanner scanner = new Scanner(System.in);
		
		int n = Integer.parseInt(br.readLine());
		
		String[] num = br.readLine().split("\\s");
			
		int count = 0;
		for(int i = 0 ; i < n ; i++) {
			count = PrimeNumber(Integer.parseInt(num[i]), count);
		}
		
		sb.append(count);
		System.out.println(sb);
	}
	
	static int PrimeNumber(int a, int count) {
		
		boolean isPrime  = true;
		for(int i = 2 ; i * i <= a ; i++) {
			if( a % i == 0) {
				isPrime = false;
				break;
			}
		}
		
		if(isPrime && a != 1) {
			count++;
		}
		
		return count;
	}
	
}