38 lines
897 B
Kotlin
38 lines
897 B
Kotlin
// Version 1.3.21
|
|
|
|
fun totient(n: Int): Int {
|
|
var tot = n
|
|
var nn = n
|
|
var i = 2
|
|
while (i * i <= nn) {
|
|
if (nn % i == 0) {
|
|
while (nn % i == 0) nn /= i
|
|
tot -= tot / i
|
|
}
|
|
if (i == 2) i = 1
|
|
i += 2
|
|
}
|
|
if (nn > 1) tot -= tot / nn
|
|
return tot
|
|
}
|
|
|
|
fun main() {
|
|
println(" n phi prime")
|
|
println("---------------")
|
|
var count = 0
|
|
for (n in 1..25) {
|
|
val tot = totient(n)
|
|
val isPrime = n - 1 == tot
|
|
if (isPrime) count++
|
|
System.out.printf("%2d %2d %b\n", n, tot, isPrime)
|
|
}
|
|
println("\nNumber of primes up to 25 = $count")
|
|
for (n in 26..100_000) {
|
|
val tot = totient(n)
|
|
if (tot == n-1) count++
|
|
if (n == 100 || n == 1000 || n % 10_000 == 0) {
|
|
System.out.printf("\nNumber of primes up to %-6d = %d\n", n, count)
|
|
}
|
|
}
|
|
}
|