Totient function: Difference between revisions
Added XPL0 example.
mNo edit summary |
(Added XPL0 example.) |
||
Line 3,505:
Number of primes up to 100000 = 9592
</pre>
=={{header|XPL0}}==
<lang XPL0>func GCD(N, D); \Return the greatest common divisor of N and D
int N, D; \numerator and denominator
int R;
[if D > N then
[R:= D; D:= N; N:= R]; \swap D and N
while D > 0 do
[R:= rem(N/D);
N:= D;
D:= R;
];
return N;
]; \GCD
func Totient(N); \Return the totient of N
int N, Phi, M;
[Phi:= 0;
for M:= 1 to N do
if GCD(M, N) = 1 then Phi:= Phi+1;
return Phi;
];
int N, Phi, Pwr, C, Limit;
[Text(0, "n phi is prime^m^j");
for N:= 1 to 25 do
[IntOut(0, N); ChOut(0, 9\tab\);
Phi:= Totient(N);
IntOut(0, Phi); ChOut(0, 9\tab\);
Text(0, if Phi = N-1 then "true" else "false");
CrLf(0);
];
CrLf(0);
for Pwr:= 2 to 4 do
[C:= 0;
Limit:= fix(Pow(10.0, float(Pwr)));
IntOut(0, Limit); ChOut(0, 9\tab\);
for N:= 1 to Limit do
[Phi:= Totient(N);
if Phi = N-1 then C:= C+1;
];
IntOut(0, C); CrLf(0);
];
]</lang>
{{out}}
<pre>
n phi is prime
1 1 false
2 1 true
3 2 true
4 2 false
5 4 true
6 2 false
7 6 true
8 4 false
9 6 false
10 4 false
11 10 true
12 4 false
13 12 true
14 6 false
15 8 false
16 8 false
17 16 true
18 6 false
19 18 true
20 8 false
21 12 false
22 10 false
23 22 true
24 8 false
25 20 false
100 25
1000 168
10000 1229
</pre>
| |||