[알고리즘] 소수 판별하기

Woong·2022년 5월 3일
0

Algorithm

목록 보기
1/1

O(1)O(1) 의 경우

  • 1, 2, 짝수의 경우 O(1)O(1) 으로 처리 (가지치기)

O(n)O(n) 의 경우 (worst case)

  • 자연수 N의 약수 a, N을 a로 나눈 몫을 b 이고, aba \le b라 할 때,
    • N=ab(,ab)N = ab (단, a\le b)
    • a 의 최대값은 aNa \le \sqrt N
    • 1aN,NbN1 \le a \le \sqrt N, \sqrt N \le b \le N
      • 위 범위에 aa 가 없으면, NN은 소수이다.
      • 이를 이용해 약수 검사 범위 단축
  • 짝수는 위에서 이미 가지치기하였으므로. 3 이상의 홀수 aa 에 대해서만 검사
public static boolean isPrime(int N) {
	if (N == 1) return false;
	if (N == 2) return true;
	else if (N % 2 == 0) return false;
    
	// N 이 약수라면, 루트N 이하의 약수를 가지므로 루트N까지만 검사. 
    //짝수도 위에서 이미 가지치기 하였으므로 2씩 증가
	for (int i = 3; i <= Math.sqrt(N); i+= 2) {
		if (N % i == 0) {
		  return false;
		}
	}
	return true;
}

0개의 댓글