수학 알고리즘 예제(1). 백준 [1978] 소수 찾기

백준[1978] - 소수 찾기

입력받은 숫자 중 소수가 몇 개인지 찾아내는 문제이다.
기본적인 문제 풀이 개념은 다음과 같다.

어떠한 수를 n이라 하자.
만약 n이 소수라면 n의 제곱근 이하의 어떠한 수로도 나누어 떨어지지 않는다.
약수는 제곱근을 기준으로 대칭적인 성질을 갖기 때문이다. 

n까지의 소수를 모두 세는 방법은 O(n^2)의 시간 복잡도를 갖지만 이 규칙을 사용하면 O(nlogn)까지 줄일 수 있다.

 

다음은 Java로 작성한 코드이다. 

import java.util.Scanner;

public class primeNumber {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int num = scan.nextInt();
		
		//수 배열
		int[] arr = new int[num];
		
		//소수 여부 배열
		boolean[] isPrime = new boolean[num];
		
		//입력
		for (int i = 0; i < num; i++) {
			arr[i] = scan.nextInt();
		}
		
		//판단
		for (int i = 0; i < num; i++) {
			isPrime[i] = prime(arr[i]);
		}
		
		//개수 count
		int count = 0;
		for (int i = 0; i < num; i++) {
			if(isPrime[i]) {
				count++;
			}
		}
		
		System.out.print(count);
		
	}
	
	//소수 여부 판단
	public static boolean prime(int x) {
		if(x == 1) {
			return false;
		}
		for (int i = 2; i*i <= x ; i++) {
			if( x % i == 0 ) {
				return false;
			}
		}
		return true;
	}

}