Totient function: Difference between revisions
Content added Content deleted
Not a robot (talk | contribs) (Add CLU) |
Not a robot (talk | contribs) (Add BCPL) |
||
Line 1,475: | Line 1,475: | ||
1000000 78498 |
1000000 78498 |
||
</pre> |
</pre> |
||
=={{header|BCPL}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="bcpl">get "libhdr" |
|||
let totient(n) = valof |
|||
$( let tot = n and i = 2 |
|||
while i*i <= n |
|||
$( if n rem i = 0 |
|||
$( while n rem i = 0 do n := n / i |
|||
tot := tot - tot/i |
|||
$) |
|||
if i=2 then i:=1 |
|||
i := i+2 |
|||
$) |
|||
resultis n>1 -> tot-tot/n, tot |
|||
$) |
|||
let start() be |
|||
$( let count = 0 |
|||
writes(" N Totient Prime*N") |
|||
for n = 1 to 25 |
|||
$( let tot = totient(n) |
|||
let prime = n-1 = tot |
|||
if prime then count := count + 1 |
|||
writef("%I2 %I7 %S*N", n, tot, prime -> " Yes", " No") |
|||
$) |
|||
writef("Number of primes up to %I6: %I4*N", 25, count) |
|||
for n = 26 to 10000 |
|||
$( if totient(n) = n-1 then count := count + 1 |
|||
if n = 100 | n = 1000 | n = 10000 then |
|||
writef("Number of primes up to %I6: %I4*N", n, count) |
|||
$) |
|||
$)</syntaxhighlight> |
|||
{{out}} |
|||
<pre> N Totient Prime |
|||
1 1 No |
|||
2 1 Yes |
|||
3 2 Yes |
|||
4 2 No |
|||
5 4 Yes |
|||
6 2 No |
|||
7 6 Yes |
|||
8 4 No |
|||
9 6 No |
|||
10 4 No |
|||
11 10 Yes |
|||
12 4 No |
|||
13 12 Yes |
|||
14 6 No |
|||
15 8 No |
|||
16 8 No |
|||
17 16 Yes |
|||
18 6 No |
|||
19 18 Yes |
|||
20 8 No |
|||
21 12 No |
|||
22 10 No |
|||
23 22 Yes |
|||
24 8 No |
|||
25 20 No |
|||
Number of primes up to 25: 9 |
|||
Number of primes up to 100: 25 |
|||
Number of primes up to 1000: 168 |
|||
Number of primes up to 10000: 1229</pre> |
|||
=={{header|BQN}}== |
=={{header|BQN}}== |