백준 1978 / 소수찾기

문제

풀이

1. 소수의 정의를 그대로 이용

n이 소수가 되려면 2보다 크거나 같고, n-1보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.
( 시간 복잡도 : 총 n번 검사하므로 O(n) )

코드

import java.util.Scanner;

public class Num1978 {
	
	static boolean prime(int n) {
		if (n < 2) {
			return false;
		}
		for (int i=2; i<=n-1; i++) {
			if(n%i == 0) {
				return false;
			}
		}
		return true;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int ans = 0;
		while (n-- > 0) {
			if(prime(sc.nextInt())) {
				ans += 1;
			}
		}
		System.out.println(ans);
	}
}

2. n/2로 나누는 방법

n이 소수가 되려면 2보다 크거나 같고, n/2보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.
이유 : N의 약수 중에서 가장 큰 것은 N/2보다 작거나 같기 때문
N = a * b로 나타낼 수 있는데, a가 작을 수록 b는 크다.
가능한 a중에서 가장 작은 값은 2이기 때문에, b는 그에 따른 가장 큰 수인 n/2를 넘지 않는다.
( 시간 복잡도 : 총 n/2번 검사하므로 상수항을 무시하기 때문에 결국 O(n) )

코드

	static boolean prime(int n) {
		if (n < 2) {
			return false;
		}
		for (int i=2; i<=n/2; i++) {
			if(n%i == 0) {
				return false;
			}
		}
		return true;
	}

3. 루트N

n이 소수가 되려면 2보다 크거나 같고, '루트n'보다 작거나 같은 자연수로 나누어 떨어지면 안 된다.
이유 : n이 소수가 아니라면, n = axb로 나타낼 수 있다. ( a<=b )
a > b라면 두 수를 바꿔서 항상 a <= b로 만들 수 있다.
두 수 a와 b의 차이가 가장 작은 경우는 루트 N이다.
따라서, 루트 N까지만 검사를 해보면 된다.
( 시간 복잡도 : O(루트n) )

코드

static boolean prime(int n) {
		if (n < 2) {
			return false;
		}
		for (int i=2; i*i<=n; i++) {
			if(n%i == 0) {
				return false;
			}
		}
		return true;
	}

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