소수 판별

소수 판별

💡

양의 약수가 1과 자기 자신 2개 뿐인 자연수

소수가 아닌 수는 합성수이다.

가장 단순한 방법

2부터 n-1까지 모든 수를 돌면서 나머지가 0이 아니면 소수이다.

조금 더 발전한 방법

합성수는 n = p*q (p, q ≠ 1, n) 형태로 나타낼 수 있다.

이때 (p≤q) 일때 p는 항상 √n 이하이고 q는 항상 √n 이상이다.

따라서 범위를 n-1까지가 아니라 √n 까지 줄일 수 있다.

코드

// 자연수 n이 소수인지 판별한다.
static boolean isPrime(int n) {
    // 1과 2는 예외처리
    if (n <= 1) {
        return false;
    }
    if (n == 2) {
        return true;
    }

    // 2를 제외한 짝수는 소수가 아니다.
    if (n % 2 == 0) {
        return false;
    }

    // 3 이상의 모든 홀수로 나눠보기
    int lastNumber = (int) Math.sqrt(n);

    // 짝수는 이미 처리되므로 2씩 증가시킨다.
    for (int div = 3; div <= lastNumber; div += 2) {
        // 합성수의 경우
        if (n % div == 0) {
            return false;
        }
    }

    // 소수의 경우
    return true;
}

---

소인수 분해

합성수를 소수들의 곱으로 표현하는 방법을 찾기

가장 쉬운 방법

2부터 시작해 n의 소인수가 될 수 있는 수를 순회하면서 n의 약수를 찾을 때 마다 n을 그 값으로 나눈다.

// 주어진 정수 n을 소인수분해하는 알고리즘
List<Integer> factorSimple(int n) {
  List<Integer> result = new ArrayList<>();

  int lastNumber = (int) Math.sqrt(n);
  for (int div = 2; div <= lastNumber; div++) {
      while (n % div == 0) {
          n /= div;
          result.add(div);
      }
  }

  if (n > 1) {
      result.add(n);
  }

  return result;
}

---

에라토스테네스의 체

n 이하의 소수를 모두 찾아내는 방법중 하나

가장 자주 사용되는 방법이다.

처음에는 2의 배수를 전부 지워나간다.

지운 결과는 다음과 같다.

이후 지워지지 않은 수는 3이다.

3의 배수를 모두 지운다.

지운 결과는 다음과 같다.

다음은 5의 배수, 그 다음은 7의 배수..를 반복하며 계속해서 지워주는 작업을 진행한다.

위 에라토스테네스의 체를 코드로 구현해보자.

static int n;
static boolean isPrime[];

static void eratosthenes() {
    isPrime = new boolean[100];
    Arrays.fill(isPrime, true);

    // 1은 항상 예외처리
    isPrime[0] = isPrime[1] = false;

    int lastNumber = (int) Math.sqrt(n);
    for (int i = 2; i <= lastNumber; i++) {
        // 이 수가 아직 지워지지 않았다면..
        if (isPrime[i]) {
            // i의 배수는 전부 합성수 처리
            // i*2, i*3 은 i가 2, 3일때 각각 처리되므로 따로 처리하지 않음
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

---

에라토스테네스의 체를 이용한 소인수 분해

에라토스테네스의 체를 이용하여 소수 판별 뿐만 아니라 소인수 분해도 가능하다.

static int n;
// i의 가장 작은 소인수
static int minFactor[];

static void eratosthenes() {
    // 0, 1은 예외처리
    minFactor[0] = minFactor[1] = -1;

    // 자기 자신으로 일단 초기화
    for (int i = 2; i <= n; i++) {
        minFactor[i] = i;
    }

    int lastNumber = (int) Math.sqrt(n);
    for (int i = 2; i <= lastNumber; i++) {
        // 자기 자신이 가장 작은 소인수인 경우 -> 소수인 경우
        if (minFactor[i] == i) {
            // i의 배수는 모두 합성수이다.
            // i의 배수의 가장 작은 소인수는 i이다.
            for (int j = i * i; j <= lastNumber; j += i) {
                minFactor[j] = i;
            }
        }
    }
}

// 2이상의 자연수 n을 소인수분해한 결과를 반환
static List<Integer> factor(int n) {
    List<Integer> result = new ArrayList<>();

    // n이 1이 될 때 까지 가장 작은 소인수로 나누기 반복
    while (n > 1) {
        result.add(minFactor[n]);
        n /= minFactor[n];
    }

    return result;
}

Uploaded by N2T