백준 - 1978번 - 소수 찾기

1978번

#1 기본 판별 법

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int num = Integer.parseInt(bf.readLine());
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int cnt = 0;
		for (int i = 0; i<num; i++) {
			if (solve(Integer.parseInt(st.nextToken()))) {
				cnt++;
			}
		}

		System.out.println(cnt);
	}

	static boolean solve(int N) {
		if (N == 1) {
			return false;
		}

		for (int i = 2; i<N; i++) {
			if (N % i == 0) {
				return false;
			}
		}

		return true;
	}
}

#2 제곱근을 이용한 기본 판별법

	static boolean solve(int N) {
		if (N == 1) {
			return false;
		}

		for (int i = 2; i<=Math.sqrt(N); i++) {
			if (N % i == 0) {
				return false;
			}
		}

		return true;
	}

#3 에라토스테네스의 체

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

	static boolean[] prime;

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int num = Integer.parseInt(bf.readLine());
		StringTokenizer st = new StringTokenizer(bf.readLine());
		int cnt = 0;

		makePrime(1000);
		for (int i = 0; i<num; i++) {
			if (prime[Integer.parseInt(st.nextToken())] == false) {
				cnt++;
			}
		}

		System.out.println(cnt);
	}
	
	static boolean[] makePrime(int N) {
		prime = new boolean[N+1];

		prime[0] = true;
		prime[1] = true;

		for (int i = 2; i<=Math.sqrt(N); i++) {
			if (prime[i]) {
				continue;
			}

			for (int j = i * i; j<N+1; j=j+i) {
				prime[j] = true;
			}
		}
		return prime;
	}
}

풀이

---

입력 받은 수가 소수인지 판별하는 문제다

소수를 찾는 메서드를 구성하는 방법은 3가지 정도있다.

#1

O(N)의 시간복잡도를 가지는 방법이다. 1이면 false, 2보다 크고 N보다 작은 경우 나누어 떨어지면 false로 나오게 한다.

2보다 큰수로 나누었을때 나누어 떨어지는 수가 없다면 true를 반환하고 이 수 가 소수다.

#2

O(√N)의 시간복잡도를 가지는 방법이다. 원리는 #1과 동일하지만 이번에는 2보다 크고 N의 제곱수까지만 판별해 준다.

예를 들어 9가 소수인지 판별할때 제곱수인 3까지만 구해보면 소수인지 알 수 있다. 3까지만 대입해보고 3은 제곱수이니까 무조건 나누어 떨어지는 수다. 그래서 false로 처리되고 그 후 수는4, 5, 6, 7, 8를 9로 무조건 안떨어지는 수 들이여서 제곱까지 나누어 떨어진 적이 없다면 true로 변환된다.

#3

O(n ㏒ (㏒ n))의 시간복잡도를 가지는 방법이다. 이 방법은 N까지 수 중 소수가 있으면 false를 나타낸다.

static boolean[] makePrime(int N) {
		prime = new boolean[N+1];

		prime[0] = true; // 0은 그냥 제외
		prime[1] = true; // 1은 소수가 아니므로 true

		// 구하려는 범위 수의 제곱근까지만 구해보면 된다.
		for (int i = 2; i<=Math.sqrt(N); i++) {
        	// true일 경우 넘어간다.
			if (prime[i]) {
				continue;
			}

			// 2부터 2의 배수는 전부 true로 바꿔준다.
            // 2의 배수를 다 찾으면 +1해서 3의 배수, 4는 위의 if문에서 걸러지고 5의 배수... 쭉간다.
			for (int j = i * i; j<N+1; j=j+i) {
				prime[j] = true;
			}
		}
		return prime;
        // 결론 소수만 기본상태인 false로 남는다.
	}