Totient function: Difference between revisions
Content added Content deleted
Not a robot (talk | contribs) (Add MAD) |
Not a robot (talk | contribs) (Add CLU) |
||
Line 1,774: | Line 1,774: | ||
Count of primes up to 10000000: 664579 |
Count of primes up to 10000000: 664579 |
||
</pre> |
</pre> |
||
=={{header|CLU}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="clu">totient = proc (n: int) returns (int) |
|||
tot: int := n |
|||
i: int := 2 |
|||
while i*i <= n do |
|||
if n//i = 0 then |
|||
while n//i = 0 do |
|||
n := n/i |
|||
end |
|||
tot := tot-tot/i |
|||
end |
|||
if i=2 then i:=1 end |
|||
i := i+2 |
|||
end |
|||
if n>1 then |
|||
tot := tot-tot/n |
|||
end |
|||
return(tot) |
|||
end totient |
|||
start_up = proc () |
|||
po: stream := stream$primary_output() |
|||
count: int := 0 |
|||
stream$putl(po, " N Totient Prime") |
|||
for n: int in int$from_to(1, 25) do |
|||
tot: int := totient(n) |
|||
stream$putright(po, int$unparse(n), 2) |
|||
stream$putright(po, int$unparse(tot), 9) |
|||
if n-1 = tot then |
|||
stream$putright(po, "Yes", 7) |
|||
count := count + 1 |
|||
else |
|||
stream$putright(po, "No", 7) |
|||
end |
|||
stream$putl(po, "") |
|||
end |
|||
stream$putl(po, "Number of primes up to 25:\t" || int$unparse(count)) |
|||
for n: int in int$from_to(26, 100000) do |
|||
if totient(n) = n-1 then |
|||
count := count + 1 |
|||
end |
|||
if n = 100 cor n = 1000 cor n // 10000 = 0 then |
|||
stream$putl(po, "Number of primes up to " |
|||
|| int$unparse(n) || ":\t" |
|||
|| int$unparse(count)) |
|||
end |
|||
end |
|||
end start_up</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 |
|||
Number of primes up to 20000: 2262 |
|||
Number of primes up to 30000: 3245 |
|||
Number of primes up to 40000: 4203 |
|||
Number of primes up to 50000: 5133 |
|||
Number of primes up to 60000: 6057 |
|||
Number of primes up to 70000: 6935 |
|||
Number of primes up to 80000: 7837 |
|||
Number of primes up to 90000: 8713 |
|||
Number of primes up to 100000: 9592</pre> |
|||
=={{header|Cowgol}}== |
=={{header|Cowgol}}== |
||
Line 1,878: | Line 1,971: | ||
Number of primes up to 90000: 8713 |
Number of primes up to 90000: 8713 |
||
Number of primes up to 100000: 9592</pre> |
Number of primes up to 100000: 9592</pre> |
||
=={{header|D}}== |
=={{header|D}}== |
||
{{trans|C}} |
{{trans|C}} |