728x90
질문: 10000000 까지의 소수 갯수는?
답: 664579
풀이 알고리즘 1)
<방법>: 3 ~ 목표지점 까지 for문을 돌고, 하나하나 소수 데이터 List를 또 돌면서 나누어 나머지가 없는지 체크한다.
<시간복잡도>: n*n
val primeList = ArrayList<Int>().apply { add(2) }
val goalNumber = 100000000
for (num in 3..goalNumber) {
/*println("num: $num")*/
var isPrime = true
primeList.forEach {
if (num % it == 0) {
isPrime = false
return@forEach
}
}
if (isPrime) primeList.add(num)
}
println("prime count: ${primeList}")
풀이 알고리즘 2)
<의문점>: 소수 리스트를 모두 돌면서 체크할 필요가 있을까?
<방법>: 검사할 대상을 y라고 한다면, y = a * b 일것이다.
y가 소수가 아니라면, a b중 작은 쪽의 최대값은 √y 최소값은 2 일 것이다.
<시간복잡도>: n*logN
val primeList = ArrayList<Int>().apply { add(2) }
val goalNumber = 1000000
for (num in 3..goalNumber) {
/*println("num: $num")*/
var isPrime = true
primeList
.filter { it <= Math.sqrt(num.toDouble()).toInt() }
.forEach {
if (num % it == 0) {
isPrime = false
return@forEach
}
}
if (isPrime) primeList.add(num)
}
루트 계산은 느리니, it <= √y 를 it * it <= √y 를 이용하겠다.
val primeList = ArrayList<Int>().apply { add(2) }
val goalNumber = 100000
for (num in 3..goalNumber) {
var isPrime = true
primeList
.forEach {
if (it * it > num) {
return@forEach
}
if (num % it == 0) {
isPrime = false
return@forEach
}
}
if (isPrime) primeList.add(num)
}
더 있을 거 같은데.. 고민 중
여러분의 더 좋은 풀이가 있다면 적고 공유 부탁드립니다!
<참고>