알고리즘 기본 - 에라토스테네스의 체

참고 블로그

https://firework-ham.tistory.com/8

[JAVA] 소수 구하는 알고리즘 : 에라토스테네스의 체

 

에라토스테네스의 체는 kks 블로그에서 이름만 보고 지레 겁먹어서 미뤘던 카테고리다.

그러다 소수 구하기 알고리즘을 보다가 우연히 발견했는데 생각보다 간단하다.

결국 소수를 구한 다음에 그 배수들을 소수에서 제외하는 방식.

자바로 구현해봤는데 구현 난이도도 굉장히 쉬웠다.

 

import java.io.IOException;
import java.util.HashMap;
import java.util.Map;


public class Main {
    static boolean[] isPrimes = new boolean[101];
    static boolean[] isCheckedNumber = new boolean[101];
    private static int getPrimeNumber(int number) {
        if (number <= 1) {
            isPrimes[number] = false;
            return -1;
        } else if (isCheckedNumber[number]) {
            return -1;
        }

        boolean isPrime = true;
        for (int i = 2; i*i <= number; i++) {
            if (number % i == 0) {
                isPrime = false;
                isPrimes[number] = false;
                break;
            }
        }

        isCheckedNumber[number] = true;
        if (isPrime) {
            deleteMultipleOfNumber(number, isPrimes);
            return number;
        } else {
            return -1;
        }
    }

    private static void deleteMultipleOfNumber(int number, boolean[] isPrimes) {
        int multipledNumber = 2;
        isPrimes[number] = true;
        while (number*multipledNumber <= isPrimes.length-1) {
            isPrimes[number*multipledNumber] = false;
            multipledNumber++;
        }
    }

    public static void main(String[] args) throws IOException {
        Map<Integer, Boolean> map = new HashMap<>();
        for (int i = 0; i < isPrimes.length; i++) {
            isPrimes[i] = true;
        }
        int[] numbers = new int[101];
        for (int i = 0; i <= 100; i++) {
            numbers[i] = i;
        }
        for (int i = 0; i <= 100; i++) {
            getPrimeNumber(i);
        }

        for (int i = 0; i < numbers.length; i++) {
            map.put(numbers[i],isPrimes[i]);
        }
        map.forEach((key, value) -> System.out.println("Key : "+key+" value : "+value));
    }
}