Totient function: Difference between revisions
Content added Content deleted
Not a robot (talk | contribs) (Add Draco) |
Not a robot (talk | contribs) (Add Modula-2) |
||
Line 3,347: | Line 3,347: | ||
1229 |
1229 |
||
9592</pre> |
9592</pre> |
||
=={{header|Modula-2}}== |
|||
<syntaxhighlight lang="modula2">MODULE TotientFunction; |
|||
FROM InOut IMPORT WriteString, WriteCard, WriteLn; |
|||
VAR count, n, tot: CARDINAL; |
|||
PROCEDURE totient(n: CARDINAL): CARDINAL; |
|||
VAR tot, i: CARDINAL; |
|||
BEGIN |
|||
tot := n; |
|||
i := 2; |
|||
WHILE i*i <= n DO |
|||
IF n MOD i = 0 THEN |
|||
WHILE n MOD i = 0 DO |
|||
n := n DIV i |
|||
END; |
|||
DEC(tot, tot DIV i) |
|||
END; |
|||
IF i=2 THEN i := 1 END; |
|||
INC(i, 2) |
|||
END; |
|||
IF n>1 THEN |
|||
DEC(tot, tot DIV n) |
|||
END; |
|||
RETURN tot |
|||
END totient; |
|||
PROCEDURE ShowPrimeCount(n, count: CARDINAL); |
|||
BEGIN |
|||
WriteString("Number of primes up to"); |
|||
WriteCard(n, 6); |
|||
WriteString(": "); |
|||
WriteCard(count, 4); |
|||
WriteLn |
|||
END ShowPrimeCount; |
|||
BEGIN |
|||
count := 0; |
|||
WriteString(" N Totient Prime"); |
|||
WriteLn; |
|||
FOR n := 1 TO 25 DO |
|||
tot := totient(n); |
|||
WriteCard(n, 2); |
|||
WriteCard(tot, 9); |
|||
IF tot = n-1 THEN |
|||
WriteString(" Yes"); |
|||
INC(count) |
|||
ELSE |
|||
WriteString(" No") |
|||
END; |
|||
WriteLn |
|||
END; |
|||
ShowPrimeCount(25, count); |
|||
FOR n := 26 TO 10000 DO |
|||
IF totient(n) = n-1 THEN INC(count) END; |
|||
IF (n=100) OR (n=1000) OR (n=10000) THEN |
|||
ShowPrimeCount(n, count) |
|||
END; |
|||
END |
|||
END TotientFunction.</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|Nim}}== |
=={{header|Nim}}== |