Perfect totient numbers: Difference between revisions
Content deleted Content added
m →{{header|REXX}}: optimized the main DO loop (twice as fast). |
→{{header|Go}}: Added much quicker version using Euler's product formula. |
||
Line 78: | Line 78: | ||
[3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571] |
[3 9 15 27 39 81 111 183 243 255 327 363 471 729 2187 2199 3063 4359 4375 5571] |
||
</pre> |
</pre> |
||
The following much quicker version uses Euler's product formula rather than repeated invocation of the gcd function to calculate the totient: |
|||
<lang go>package main |
|||
import "fmt" |
|||
func totient(n int) int { |
|||
tot := n |
|||
for i := 2; i*i <= n; i += 2 { |
|||
if n%i == 0 { |
|||
for n%i == 0 { |
|||
n /= i |
|||
} |
|||
tot -= tot / i |
|||
} |
|||
if i == 2 { |
|||
i = 1 |
|||
} |
|||
} |
|||
if n > 1 { |
|||
tot -= tot / n |
|||
} |
|||
return tot |
|||
} |
|||
func main() { |
|||
var perfect []int |
|||
for n := 1; len(perfect) < 20; n += 2 { |
|||
tot := n |
|||
sum := 0 |
|||
for tot != 1 { |
|||
tot = totient(tot) |
|||
sum += tot |
|||
} |
|||
if sum == n { |
|||
perfect = append(perfect, n) |
|||
} |
|||
} |
|||
fmt.Println("The first 20 perfect totient numbers are:") |
|||
fmt.Println(perfect) |
|||
}</lang> |
|||
The output is the same as before. |
|||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |