에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. 알고리즘[편집] 2부터 소수
ko.wikipedia.org
[ Code ]
특정 수의 소수를 구하는 방식
fun sieveOfEratosthenes(n: Int): List<Int> {
val isPrime = BooleanArray(n + 1) { true }
val primes = mutableListOf<Int>()
for (p in 2..n) {
if (isPrime[p]) {
primes.add(p)
for (i in p * p..n step p) { isPrime[i] = false }
}
}
return primes
}
특정 수들의 범위 안의 소수를 구하는 방식
fun sieveOfEratosthenes(start: Int, end: Int): List<Int> {
val primes = mutableListOf<Int>()
val isPrime = BooleanArray(end - start + 1) { true }
val sqrtEnd = sqrt(end.toDouble()).toInt()
for (p in 2..sqrtEnd) {
for (i in maxOf(p * p, (start + p - 1) / p * p) until end + 1 step p) { isPrime[i - start] = false }
}
for (i in isPrime.indices) { if (isPrime[i]) primes.add(start + i) }
return primes
}