에라토스테네스의 체(소수, 약수 구하기)

◇ 알고리즘 정의

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법.

이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네스의 체'라고 부른다. 

 

◇ 알고리즘 동장방식

출처 : https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

에라토스테네스의 체

 

◇ 알고리즘 구현

public class Main {
    public static void main(String[] args) {
    	int number = 9;
        int[] factors = new int[number + 1];

        // 에라토스테네스의 체 변형을 사용하여 약수의 개수 계산
        for (int i = 1; i <= number; i++) {
            for (int j = i; j <= number; j += i) {
                factors[j]++;
            }
        }

9까지의 for문 루프를 나타내보면

 

• i = 1:
  • j는 1부터 9까지 1씩 증가하며 factors[j] 값을 증가시킵니다.
  • factors = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1]
• i = 2:
  • j는 2부터 9까지 2씩 증가하며 factors[j] 값을 증가시킵니다.
  • factors = [0, 1, 2, 1, 2, 1, 2, 1, 2, 1]
• i = 3:
  • j는 3부터 9까지 3씩 증가하며 factors[j] 값을 증가시킵니다.
  • factors = [0, 1, 2, 2, 2, 1, 2, 1, 2, 2]
• i = 4:
  • j는 4부터 8까지 4씩 증가하며 factors[j] 값을 증가시킵니다.
  • factors = [0, 1, 2, 2, 3, 1, 2, 1, 3, 2]
• i = 5:
  • j는 5부터 5까지 5씩 증가하며 factors[j] 값을 증가시킵니다.
  • factors = [0, 1, 2, 2, 3, 2, 2, 1, 3, 2]
• i = 6:
  • j는 6부터 6까지 6씩 증가하며 factors[j] 값을 증가시킵니다.
  • factors = [0, 1, 2, 2, 3, 2, 3, 1, 3, 2]
• i = 7:
  • j는 7부터 7까지 7씩 증가하며 factors[j] 값을 증가시킵니다.
  • factors = [0, 1, 2, 2, 3, 2, 3, 2, 3, 2]
• i = 8:
  • j는 8부터 8까지 8씩 증가하며 factors[j] 값을 증가시킵니다.
  • factors = [0, 1, 2, 2, 3, 2, 3, 2, 4, 2]
• i = 9:
  • j는 9부터 9까지 9씩 증가하며 factors[j] 값을 증가시킵니다.
  • factors = [0, 1, 2, 2, 3, 2, 3, 2, 4, 3]

다음과 같다.

수 i의 배수를 인덱스로 갖는 배열 arr[j]의 값을 1씩 증가시키는 개념이다.