Totient function: Difference between revisions

=={{header|RPL}}==

===GCD approach===

Very compact code, but very slow algorithm.

≪ → n

≪ 0 1 n FOR j

n j

WHILE DUP REPEAT SWAP OVER MOD END

DROP 1 == +

NEXT

≫ ≫

‘PHI’ STO

≪ 1 1 ROT FOR j

j DUP PHI - 1 == +

2 STEP

≫

'CNTPR' STO

25 PHI

10000 CNTPR

{{out}}

<pre>

2: 20

1: 1229

</pre>

===Faster version===

{{trans|C}}

Calculator simulator's timedog unfortunately prevents from running the code to count up to 100,000.

{{works with|Halcyon Calc|4.2.7}}

≪ DUP 2 OVER √

FOR j

IF DUP j MOD NOT THEN

WHILE DUP j MOD NOT REPEAT

j /

END

SWAP DUP j / - SWAP

END

IF j 2 == THEN 1 'j' STO END

2 STEP

IF DUP 1 > THEN OVER SWAP / - ELSE DROP END

≫

‘PHI’ STO