Totient function: Difference between revisions
Content added Content deleted
mNo edit summary |
(Added XPL0 example.) |
||
Line 3,505: | Line 3,505: | ||
Number of primes up to 100000 = 9592 |
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> |
</pre> |
||