40 lines
1.1 KiB
Text
40 lines
1.1 KiB
Text
fun countPrimes(lmt: Long): Long {
|
|
if (lmt < 3) return if (lmt < 2) 0 else 1
|
|
val sqrtlmt = Math.sqrt(lmt.toDouble()).toInt()
|
|
fun makePrimes(): IntArray {
|
|
val mxndx = (sqrtlmt - 3) / 2
|
|
val arr = IntArray(mxndx + 1, { it + it + 3})
|
|
var i = 0
|
|
while (true) {
|
|
val sqri = (i + i) * (i + 3) + 3
|
|
if (sqri > mxndx) break
|
|
if (arr[i] != 0) {
|
|
val bp = i + i + 3
|
|
for (c in sqri .. mxndx step bp) arr[c] = 0
|
|
}
|
|
i++
|
|
}
|
|
return arr.filter { it != 0 }.toIntArray()
|
|
}
|
|
val oprms = makePrimes()
|
|
fun phi(x: Long, a: Int): Long {
|
|
if (a <= 0) return x - (x shr 1)
|
|
val na = a - 1; val p = oprms[na].toLong()
|
|
if (x <= p) return 1
|
|
return phi(x, na) - phi(x / p, na)
|
|
}
|
|
return phi(lmt, oprms.size) + oprms.size.toLong()
|
|
}
|
|
|
|
fun main() {
|
|
val strt = System.currentTimeMillis()
|
|
|
|
for (i in 0 .. 9) {
|
|
val arg = Math.pow(10.toDouble(), i.toDouble()).toLong()
|
|
println("π(10**$i) = ${countPrimes(arg)}")
|
|
}
|
|
|
|
val stop = System.currentTimeMillis()
|
|
|
|
println("This took ${stop - strt} milliseconds.")
|
|
}
|