에라토스테네스의 체

gistfile1.md

// '에라토스테네스의 체'로 n개의 범위의 소수들을 구하는 방법.
public int[] primes(int n) {
  int [] datas = new int[n+1];
  for(int i = 2; i <= n; i++) {
    datas[i] = i;
  }

  for(int i = 2; i <= n; i++) {
    if (datas[i] == 0) {
      continue;
    }
    for(int j = i * 2; j <= n; j += i) {
      // i의 배수를 0으로 바꿈.
      datas[j] = 0;
    }
  }
  return datas;
}