68 lines
1.2 KiB
Go
68 lines
1.2 KiB
Go
package main
|
|
|
|
import "fmt"
|
|
|
|
func gcd(n, k int) int {
|
|
if n < k || k < 1 {
|
|
panic("Need n >= k and k >= 1")
|
|
}
|
|
|
|
s := 1
|
|
for n&1 == 0 && k&1 == 0 {
|
|
n >>= 1
|
|
k >>= 1
|
|
s <<= 1
|
|
}
|
|
|
|
t := n
|
|
if n&1 != 0 {
|
|
t = -k
|
|
}
|
|
for t != 0 {
|
|
for t&1 == 0 {
|
|
t >>= 1
|
|
}
|
|
if t > 0 {
|
|
n = t
|
|
} else {
|
|
k = -t
|
|
}
|
|
t = n - k
|
|
}
|
|
return n * s
|
|
}
|
|
|
|
func totient(n int) int {
|
|
tot := 0
|
|
for k := 1; k <= n; k++ {
|
|
if gcd(n, k) == 1 {
|
|
tot++
|
|
}
|
|
}
|
|
return tot
|
|
}
|
|
|
|
func main() {
|
|
fmt.Println(" n phi prime")
|
|
fmt.Println("---------------")
|
|
count := 0
|
|
for n := 1; n <= 25; n++ {
|
|
tot := totient(n)
|
|
isPrime := n-1 == tot
|
|
if isPrime {
|
|
count++
|
|
}
|
|
fmt.Printf("%2d %2d %t\n", n, tot, isPrime)
|
|
}
|
|
fmt.Println("\nNumber of primes up to 25 =", count)
|
|
for n := 26; n <= 100000; n++ {
|
|
tot := totient(n)
|
|
if tot == n-1 {
|
|
count++
|
|
}
|
|
if n == 100 || n == 1000 || n%10000 == 0 {
|
|
fmt.Printf("\nNumber of primes up to %-6d = %d\n", n, count)
|
|
}
|
|
}
|
|
}
|