57 lines
2 KiB
Kotlin
57 lines
2 KiB
Kotlin
val cTinyPhiPrimes = intArrayOf(2, 3, 5, 7, 11, 13)
|
|
val cTinyPhiDeg = cTinyPhiPrimes.size - 1
|
|
val cTinyPhiOddCirc = cTinyPhiPrimes.reduce(Int::times) / 2
|
|
val cTinyPhiTot = cTinyPhiPrimes.fold(1) { s, p -> s * (p - 1) }
|
|
fun makeTPLUT(): IntArray {
|
|
val arr = IntArray(cTinyPhiOddCirc) { _ -> 1 }
|
|
for (bp in cTinyPhiPrimes.drop(1)) {
|
|
arr[bp shr 1] = 0
|
|
for (c in ((bp * bp) shr 1) until cTinyPhiOddCirc step bp) arr[c] = 0 }
|
|
var acc = 0
|
|
for (i in 0 until cTinyPhiOddCirc) { acc += arr[i]; arr[i] = acc }
|
|
return arr
|
|
}
|
|
val cTinyPhiLUT = makeTPLUT()
|
|
fun tinyPhi(x: Long): Long {
|
|
val ndx = (x - 1) shr 1; val numtots = ndx / cTinyPhiOddCirc.toLong()
|
|
val rem = (ndx - numtots * cTinyPhiOddCirc.toLong()).toInt()
|
|
return numtots * cTinyPhiTot.toLong() + cTinyPhiLUT[rem].toLong()
|
|
}
|
|
|
|
fun countPrimes(lmt: Long): Long {
|
|
if (lmt < 169) {
|
|
if (lmt < 3) return if (lmt < 2) 0 else 1
|
|
// adjust for the missing "degree" base primes
|
|
if (lmt <= 13)
|
|
return ((lmt - 1).toLong() shr 1) + (if (lmt < 9) 1 else 0);
|
|
return 5.toLong() + cTinyPhiLUT[(lmt - 1).toInt() shr 1].toLong();
|
|
}
|
|
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 lvl(pilmt: Int, m: Long): Long {
|
|
var acc = 0.toLong()
|
|
for (pi in cTinyPhiDeg until pilmt) {
|
|
val p = oprms[pi].toLong(); val nm = m * p
|
|
if (lmt <= nm * p) return acc + (pilmt - pi).toLong()
|
|
val q = (lmt.toDouble() / nm.toDouble()).toLong(); acc += tinyPhi(q)
|
|
if (pi > cTinyPhiDeg) acc -= lvl(pi, nm)
|
|
}
|
|
return acc
|
|
}
|
|
return tinyPhi(lmt) - lvl(oprms.size, 1) + oprms.size.toLong()
|
|
}
|