30 lines
991 B
Forth
30 lines
991 B
Forth
: totient \ n -- n' ;
|
|
DUP DUP 2 ?DO ( tot n )
|
|
DUP I DUP * < IF LEAVE THEN \ for(i=2;i*i<=n;i+=2){
|
|
DUP I MOD 0= IF \ if(n%i==0){
|
|
BEGIN DUP I /MOD SWAP 0= WHILE ( tot n n/i ) \ while(n%i==0);
|
|
NIP ( tot n/i ) \ n/=i;
|
|
REPEAT
|
|
DROP ( tot n ) \ Remove the new n on exit from loop
|
|
SWAP DUP I / - SWAP ( tot' n ) \ tot-=tot/i;
|
|
THEN
|
|
2 I 2 = + +LOOP \ If I = 2 add 1 else add 2 to loop index.
|
|
DUP 1 > IF OVER SWAP / - ELSE DROP THEN ;
|
|
|
|
: bool. \ f -- ;
|
|
IF ." True " ELSE ." False" THEN ;
|
|
|
|
: count-primes \ n -- n' ;
|
|
0 SWAP 2 ?DO I DUP totient 1+ = - LOOP ;
|
|
|
|
: challenge \ -- ;
|
|
CR ." n φ prime" CR
|
|
26 1 DO
|
|
I 3 .r
|
|
I totient DUP 4 .r 4 SPACES
|
|
1+ I = bool. CR
|
|
LOOP CR
|
|
100001 100 DO
|
|
." Number of primes up to " I 6 .R ." is " I count-primes 4 .R CR
|
|
I 9 * +LOOP ;
|