Challenge | 10,000,000 까지의 소수 갯수는?

질문: 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)
}

 

더 있을 거 같은데.. 고민 중

---

여러분의 더 좋은 풀이가 있다면 적고 공유 부탁드립니다!

 

 

<참고>

https://xeriars.tistory.com/45