Totient function: Difference between revisions
Content added Content deleted
(→{{header|ALGOL 68}}: Avoid line wrap) |
Not a robot (talk | contribs) (Add SETL) |
||
Line 5,137: | Line 5,137: | ||
10000: 1229 |
10000: 1229 |
||
100000: 9592</pre> |
100000: 9592</pre> |
||
=={{header|SETL}}== |
|||
<syntaxhighlight lang="setl">program totient; |
|||
loop for n in [1..1000000] do |
|||
tot := totient(n); |
|||
if tot = n-1 then prime +:= 1; end if; |
|||
if n <= 25 then |
|||
print(lpad(str n, 2), " ", |
|||
lpad(str tot, 2), " ", |
|||
if tot = n-1 then "prime" else "" end if); |
|||
end if; |
|||
if n in [1000,10000,100000,1000000] then |
|||
print(lpad(str prime,8), "primes up to" + lpad(str n,8)); |
|||
end if; |
|||
end loop; |
|||
proc totient(n); |
|||
tot := n; |
|||
i := 2; |
|||
loop while i*i <= n do |
|||
if n mod i = 0 then |
|||
loop while n mod i = 0 do |
|||
n div:= i; |
|||
end loop; |
|||
tot -:= tot div i; |
|||
end if; |
|||
if i=2 then i:=3; |
|||
else i+:=2; |
|||
end if; |
|||
end loop; |
|||
if n>1 then |
|||
tot -:= tot div n; |
|||
end if; |
|||
return tot; |
|||
end proc; |
|||
end program;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 1 1 |
|||
2 1 prime |
|||
3 2 prime |
|||
4 2 |
|||
5 4 prime |
|||
6 2 |
|||
7 6 prime |
|||
8 4 |
|||
9 6 |
|||
10 4 |
|||
11 10 prime |
|||
12 4 |
|||
13 12 prime |
|||
14 6 |
|||
15 8 |
|||
16 8 |
|||
17 16 prime |
|||
18 6 |
|||
19 18 prime |
|||
20 8 |
|||
21 12 |
|||
22 10 |
|||
23 22 prime |
|||
24 8 |
|||
25 20 |
|||
168 primes up to 1000 |
|||
1229 primes up to 10000 |
|||
9592 primes up to 100000 |
|||
78498 primes up to 1000000</pre> |
|||
=={{header|Shale}}== |
=={{header|Shale}}== |