소수(prime number) 인지 아닌지 확인.

소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다.

 

소수 를 구하는 여러가지 방법들있고 어떻게 작동 하는지 + 어떤게 효율적인지 확인 하겠습니다.

 

1. good  (별로 추천 안함 밑에 better 을 보세요)

제일 간단하고 설명 하기 쉬운 논리의 방법

static boolean isPrime(int n)
{
  // Corner case
  if (n <= 1)
    return false;

  // Check from 2 to n-1
  for (int i = 2; i < n; i++)
    if (n % i == 0)
      return false;

  return true;
}

Time complexity(시간 복잡도):  O(n) 

Space complexity (공간 복잡도) : O(1)

 

하지만 사실상 n 의 절반 까지만 나누어 봐도 소수 인지 아닌지 확인 가능 하기 때문에 개선이 가능 하다. 

(i 로 나눌수 있으면 i*2 로 나누어 지는거 는 같기 때문에).

static boolean isPrime(int n)
{
  // Corner case
  if (n <= 1)
    return false;

  // Check from 2 to n/2
  for (int i = 2; i <= n / 2; i++)
    if (n % i == 0)
      return false;

  return true;
}

Time complexity(시간 복잡도):  O(n) 

Space complexity (공간 복잡도) : O(1)

 

 

 

2. better

n까지 확인하는 대신

 √n까지 확인 하는 수가 있습니다.

n의 더 큰 인수는 이미 확인된 작은 인수의 배수여야 하기 때문.

public boolean isPrime(long n) {
  if (n == 1) return false;
  if (n == 2) return true;

  int count = 0;

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

  return true;
}

 

원리는 n 의 약수는 항상 제곱근보다 작은 수가 존재하며 그 작은 수는 제곱근보다 큰 수와 짝을 이룬다.

 

예를 들어 100의 약수를 구하면 다음과 같다.
1,2,4,5,10,20,25,50,100
100의 제곱근은 10이기 때문에 10을 기준으로 10보다 작은 약수는 “1,2,4,5” 가 있고 각각의 짝 (곱해서 100이 되는)은 “100,50,25,20” 이므로
제곱근보다 작은 수들 중에 약수가 존재하지 않는 다면 큰 수에서도 존재하지 않는다.

 

Time complexity: O(√n)

Space complexity: O(1)

 

 

 

더 효율적인 방법은 n이 2 또는 3으로 나누어지는지 테스트한 

다음 6k ± 1 ≤ √n 형식의 모든 숫자를 확인하는 것입니다. 

이 접근 방식은 최대 √n까지의 모든 숫자를 테스트하는 것보다 3배 빠릅니다.

 

static boolean isPrime(int n)
{
  // Corner case
  if (n <= 1)
    return false;

  if (n == 2 || n == 3)
    return true;

  if (n % 2 == 0 || n % 3 == 0)
    return false;

  for (int i = 5; i <= Math.sqrt(n); i = i + 6)
    if (n % i == 0 || n % (i + 2) == 0)
      return false;

  return true;
}

 

 

Time complexity: O(√n)

Space complexity: O(1)