에라토스테네스의 체

에라토스테네스의 체 - 위키

 

10억(1024 x 1024 x 1024) 까지의 소수를 확인할 때 필요한 메모리

boolean[] isPrime = new boolean[1024*1024*1024];

boolean형 10억개 -> 1byte * 1024 * 1024 * 1024 -> 1GB

힙메모리가 1GB 이상 필요함.

   

Q. 1 ~ 123456 소수 찾기

  final int MAX_N = 123456;

  boolean[] isPrime = new boolean[MAX_N + 1];

  Arrays.fill(isPrime, true);
  isPrime[0] = false; // 0은 소수 X
  isPrime[1] = false; // 1은 소수 X

  IntStream.rangeClosed(2, MAX_N)
                .filter(i -> isPrime[i] == true)
                .forEach(i -> {
                  for (int j = i * 2; j <= MAX_N; j += i) isPrime[j] = false;
                });

  System.out.println(isPrime[7]); // true