42 lines
782 B
Plaintext
42 lines
782 B
Plaintext
func totient(n) {
|
|
var tot = n
|
|
var i = 2
|
|
while i * i <= n {
|
|
if n % i == 0 {
|
|
while n % i == 0 {
|
|
n /= i
|
|
}
|
|
tot -= tot / i
|
|
}
|
|
if i == 2 {
|
|
i = 1
|
|
}
|
|
i += 2
|
|
}
|
|
if n > 1 {
|
|
tot -= tot / n
|
|
}
|
|
return tot
|
|
}
|
|
|
|
print("n\tphi\tprime")
|
|
var count = 0
|
|
for n in 1..25 {
|
|
var tot = totient(n)
|
|
var isPrime = n - 1 == tot
|
|
if isPrime {
|
|
count += 1
|
|
}
|
|
print("\(n)\t\(tot)\t\(isPrime)")
|
|
}
|
|
print("\nNumber of primes up to 25 \t= \(count)")
|
|
for n in 26..100000 {
|
|
var tot = totient(n)
|
|
if tot == n - 1 {
|
|
count += 1
|
|
}
|
|
if n == 100 || n == 1000 || n % 10000 == 0 {
|
|
print("Number of primes up to \(n) \t= \(count)")
|
|
}
|
|
}
|