[JAVA] 백준 1978 - 소수 찾기

문제 풀이 전 이론 - 1

- 소수는 약수가 1과 자기 자신 밖에 없는 수이다.

- N이 소수이기 위해서는 N/(2-(N-1))이 0으로 나누어 떨어져서는 안된다.

- 소수를 구하는 방법은 두가지가 있다.

- 1. 어떤 수 N이 소수인지 아닌지를 판별한다.(효율성을 크게 안따져도 되는 경우)

- 2. N이하의 모든 소수를 다 구한다.(N의 맥시멈이 100만이어서 미리 저장해놓아야 하는 경우)

- 해당 문제는 N의 최악의 경우가 치명적이지 않으므로 첫 번째 방법을 사용해보겠다.

 

문제 풀이 전 이론 - 2

- 어떤 수 N이 소수인지 아닌지를 판별하기 위해서는 N을 2~N-1로 나누었을 때 0이 나오는지 살펴보면 된다.

- 하지만, 굳이 N-1까지 반복해볼 필요도 없다. 약수 파트에서 살펴보았듯이 약수는 대칭 관계가 있기 때문에 $\sqrt{N}$까지만 반복해보면 된다.

public class Main {

	public static void main(String[] args) {
		int a, n, cnt =0; // 개수
		boolean array[];
		
		Scanner scan = new Scanner(System.in);
		a = scan.nextInt();
		array = new boolean[a];
		for(int i = 0; i < array.length; i++) {
			
			n = scan.nextInt();
			array[i] = primenum(n);
		}
		
		for(int i =0; i < array.length; i ++) {
			if(array[i] == true) {
				cnt++;
			}
		}
		System.out.print(cnt);
	}
	
	public static Boolean primenum(int n) {
		
		if(n < 2) {
			return false;
		}
		for(int i = 2; i*i <= n; i++) { // 루트n까지만 반복해서 구함
			if(n % i == 0) {
				return false;
			}
		}
		return true;
	}
}

출력

문제로부터 얻어간 것

소수에는 약수 이론이 포함되어 있기 때문에 약수에서 배웠던 이론을 사용할 수 있었다. 굳이 N까지 나눠보지 않더라도 $\sqrt{N}$까지만 나누면 충분히 약수를 알 수 있다는 것이다. 그리고 $\sqrt{N}$은 i*i<=n으로 대체하여 정수 표현을 사용하는 것도 좋은 방법이다.

 

느낀점

해당 문제는 N의 최악의 경우가 시간 제한에 치명적이지 않기 때문에 첫 번째 방법을 이용하여 어렵지 않게 풀었지만, 만약 시간 제한이 치명적이라면 두 번째 방법을 사용해야 할 것이다. 이를 통해 실행 시간을 미리 예측하여 어떤 방법으로 풀지 고민해보는게 매우 중요한 것임을 알았다.