Totient function: Difference between revisions

From Rosetta Code
Content added Content deleted
(add PicoLisp)
Line 1,159: Line 1,159:
Number of primes up to 100000 = 9592
Number of primes up to 100000 = 9592
</pre>
</pre>

=={{header|PicoLisp}}==
<lang PicoLisp>(gc 32)
(de gcd (A B)
(until (=0 B)
(let M (% A B)
(setq A B B M) ) )
(abs A) )
(de totient (N)
(let C 0
(for I N
(and (=1 (gcd N I)) (inc 'C)) )
(cons C (= C (dec N))) ) )
(de p? (N)
(let C 0
(for A N
(and
(cdr (totient A))
(inc 'C) ) )
C ) )
(let Fmt (3 7 10)
(tab Fmt "N" "Phi" "Prime?")
(tab Fmt "-" "---" "------")
(for N 25
(tab Fmt
N
(car (setq @ (totient N)))
(cdr @) ) ) )
(println
(mapcar p? (25 100 1000 10000 100000)) )</lang>
{{out}}
<pre> N Phi Prime?
- --- ------
1 1
2 1 T
3 2 T
4 2
5 4 T
6 2
7 6 T
8 4
9 6
10 4
11 10 T
12 4
13 12 T
14 6
15 8
16 8
17 16 T
18 6
19 18 T
20 8
21 12
22 10
23 22 T
24 8
25 20
(9 25 168 1229 9592)</pre>


=={{header|Python}}==
=={{header|Python}}==

Revision as of 12:52, 5 July 2019

Task
Totient function
You are encouraged to solve this task according to the task description, using any language you may know.

The   totient   function is also known as:

  •   Euler's totient function
  •   Euler's phi totient function
  •   phi totient function
  •   Φ   function   (uppercase Greek phi)
  •   φ   function   (lowercase Greek phi)


Definitions   (as per number theory)

The totient function:

  •   counts the integers up to a given positive integer   n   that are relatively prime to   n
  •   counts the integers   k   in the range   1 ≤ k ≤ n   for which the greatest common divisor   gcd(n,k)   is equal to   1
  •   counts numbers   ≤ n   and   prime to   n


If the totient number   (for N)   is one less than   N,   then   N   is prime.


Task

Create a   totient   function and:

  •   Find and display   (1 per line)   for the 1st   25   integers:
  •   the integer   (the index)
  •   the totient number for that integer
  •   indicate if that integer is prime
  •   Find and display the   count   of the primes up to          100
  •   Find and display the   count   of the primes up to       1,000
  •   Find and display the   count   of the primes up to     10,000
  •   Find and display the   count   of the primes up to   100,000     (optional)

Show all output here.


Related task


Also see


AWK

<lang AWK>

  1. syntax: GAWK -f TOTIENT_FUNCTION.AWK

BEGIN { 

   print(" N Phi isPrime")
   for (n=1; n<=1000000; n++) {
     tot = totient(n)
     if (n-1 == tot) {
       count++
     }
     if (n <= 25) {
       printf("%2d %3d %s\n",n,tot,(n-1==tot)?"true":"false")
       if (n == 25) {
         printf("\n  Limit PrimeCount\n")
         printf("%7d %10d\n",n,count)
       }
     }
     else if (n ~ /^100+$/) {
       printf("%7d %10d\n",n,count)
     }
   }
   exit(0)

} function totient(n, i,tot) { 

   tot = n
   for (i=2; i*i<=n; i+=2) {
     if (n % i == 0) {
       while (n % i == 0) {
         n /= i
       }
       tot -= tot / i
     }
     if (i == 2) {
       i = 1
     }
   }
   if (n > 1) {
     tot -= tot / n
   }
   return(tot)

} </lang>

Output:
 N Phi isPrime
 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

  Limit PrimeCount
     25          9
    100         25
   1000        168
  10000       1229
 100000       9592
1000000      78498

C

Translation of the second Go example <lang C> /*Abhishek Ghosh, 7th December 2018*/

  1. include<stdio.h>

int totient(int n){ int tot = n,i;

for(i=2;i*i<=n;i+=2){ if(n%i==0){ while(n%i==0) n/=i; tot-=tot/i; }

if(i==2) i=1; }

if(n>1) tot-=tot/n;

return tot; }

int main() { int count = 0,n,tot;

printf(" n %c prime",237); 

       printf("\n---------------\n");

for(n=1;n<=25;n++){ tot = totient(n);

if(n-1 == tot) count++;

printf("%2d %2d %s\n", n, tot, n-1 == tot?"True":"False"); }

printf("\nNumber of primes up to %6d =%4d\n", 25,count);

for(n = 26; n <= 100000; n++){ 

       tot = totient(n);
       if(tot == n-1)

count++; 

       if(n == 100 || n == 1000 || n%10000 == 0){
           printf("\nNumber of primes up to %6d = %4d\n", n, count);
       }
   }

return 0; } </lang>

Output : 

 n    φ   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

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

Number of primes up to  20000 = 2262

Number of primes up to  30000 = 3245

Number of primes up to  40000 = 4203

Number of primes up to  50000 = 5133

Number of primes up to  60000 = 6057

Number of primes up to  70000 = 6935

Number of primes up to  80000 = 7837

Number of primes up to  90000 = 8713

Number of primes up to 100000 = 9592

C#

<lang csharp>using static System.Console; using static System.Linq.Enumerable;

public class Program { 

   static void Main()
   {
       for (int i = 1; i <= 25; i++) {
           int t = Totient(i);
           WriteLine(i + "\t" + t + (t == i - 1 ? "\tprime" : ""));
       }
       WriteLine();
       for (int i = 100; i <= 100_000; i *= 10) {
           WriteLine($"{Range(1, i).Count(x => Totient(x) + 1 == x):n0} primes below {i:n0}");
       }
   }

   static int Totient(int n) {
       if (n < 3) return 1;
       if (n == 3) return 2;

       int totient = n;

       if ((n & 1) == 0) {
           totient >>= 1;
           while (((n >>= 1) & 1) == 0) ;
       }

       for (int i = 3; i * i <= n; i += 2) {
           if (n % i == 0) {
               totient -= totient / i;
               while ((n /= i) % i == 0) ;
           }
       }
       if (n > 1) totient -= totient / n;
       return totient;
   }

}</lang>

Output:
1	1
2	1	prime
3	2	prime
4	2
5	4	prime
6	2
7	6	prime
8	4
9	6
10	4
11	10	prime
12	4
13	12	prime
14	6
15	8
16	8
17	16	prime
18	6
19	18	prime
20	8
21	12
22	10
23	22	prime
24	8
25	20

25 primes below 100
168 primes below 1,000
1,229 primes below 10,000
9,592 primes below 100,000

Factor

<lang factor>USING: combinators formatting io kernel math math.primes.factors math.ranges sequences ; IN: rosetta-code.totient-function

Φ ( n -- m )
   {
       { [ dup 1 < ] [ drop 0 ] }
       { [ dup 1 = ] [ drop 1 ] }
       [
           dup unique-factors
           [ 1 [ 1 - * ] reduce ] [ product ] bi / *
       ]
   } cond ;
show-info ( n -- )
   [ Φ ] [ swap 2dup - 1 = ] bi ", prime" "" ?
   "Φ(%2d) = %2d%s\n" printf ;
totient-demo ( -- )
   25 [1,b] [ show-info ] each nl 0 100,000 [1,b] [
       [ dup Φ - 1 = [ 1 + ] when ]
       [ dup { 100 1,000 10,000 100,000 } member? ] bi
       [ dupd "%4d primes <= %d\n" printf ] [ drop ] if
   ] each drop ;

MAIN: totient-demo</lang>

Output:
Φ( 1) =  1
Φ( 2) =  1, prime
Φ( 3) =  2, prime
Φ( 4) =  2
Φ( 5) =  4, prime
Φ( 6) =  2
Φ( 7) =  6, prime
Φ( 8) =  4
Φ( 9) =  6
Φ(10) =  4
Φ(11) = 10, prime
Φ(12) =  4
Φ(13) = 12, prime
Φ(14) =  6
Φ(15) =  8
Φ(16) =  8
Φ(17) = 16, prime
Φ(18) =  6
Φ(19) = 18, prime
Φ(20) =  8
Φ(21) = 12
Φ(22) = 10
Φ(23) = 22, prime
Φ(24) =  8
Φ(25) = 20

  25 primes <= 100
 168 primes <= 1000
1229 primes <= 10000
9592 primes <= 100000

Go

Results for the larger values of n are very slow to emerge. <lang go>package main

import "fmt"

func gcd(n, k int) int { 

   if n < k || k < 1 {
       panic("Need n >= k and k >= 1")
   }

   s := 1
   for n&1 == 0 && k&1 == 0 {
       n >>= 1
       k >>= 1
       s <<= 1
   }

   t := n
   if n&1 != 0 {
       t = -k
   }
   for t != 0 {
       for t&1 == 0 {
           t >>= 1
       }
       if t > 0 {
           n = t
       } else {
           k = -t
       }
       t = n - k
   }
   return n * s

}

func totient(n int) int { 

   tot := 0
   for k := 1; k <= n; k++ {
       if gcd(n, k) == 1 {
           tot++
       }
   }
   return tot

}

func main() { 

   fmt.Println(" n  phi   prime")
   fmt.Println("---------------")
   count := 0
   for n := 1; n <= 25; n++ {
       tot := totient(n)
       isPrime := n-1 == tot
       if isPrime {
           count++
       }
       fmt.Printf("%2d   %2d   %t\n", n, tot, isPrime)
   }
   fmt.Println("\nNumber of primes up to 25     =", count)
   for n := 26; n <= 100000; n++ {
       tot := totient(n)
       if tot == n-1 {
           count++
       }
       if n == 100 || n == 1000 || n%10000 == 0 {
           fmt.Printf("\nNumber of primes up to %-6d = %d\n", n, count)
       }
   }

}</lang>

Output:
 n  phi   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

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

Number of primes up to 20000  = 2262

Number of primes up to 30000  = 3245

Number of primes up to 40000  = 4203

Number of primes up to 50000  = 5133

Number of primes up to 60000  = 6057

Number of primes up to 70000  = 6935

Number of primes up to 80000  = 7837

Number of primes up to 90000  = 8713

Number of primes up to 100000 = 9592

The following much quicker version (runs in less than 150 ms on my machine) uses Euler's product formula rather than repeated invocation of the gcd function to calculate the totient:

<lang go>package main

import "fmt"

func totient(n int) int { 

   tot := n
   for i := 2; i*i <= n; i += 2 {
       if n%i == 0 {
           for n%i == 0 {
               n /= i
           }
           tot -= tot / i
       }
       if i == 2 {
           i = 1
       }
   }
   if n > 1 {
       tot -= tot / n
   }
   return tot

}

func main() { 

   fmt.Println(" n  phi   prime")
   fmt.Println("---------------")
   count := 0
   for n := 1; n <= 25; n++ {
       tot := totient(n)
       isPrime := n-1 == tot
       if isPrime {
           count++
       }
       fmt.Printf("%2d   %2d   %t\n", n, tot, isPrime)
   }
   fmt.Println("\nNumber of primes up to 25     =", count)
   for n := 26; n <= 100000; n++ {
       tot := totient(n)
       if tot == n-1 {
           count++
       }
       if n == 100 || n == 1000 || n%10000 == 0 {
           fmt.Printf("\nNumber of primes up to %-6d = %d\n", n, count)
       }
   }

}</lang>

The output is the same as before.

J

<lang J> 

 nth_prime =: p:   NB. 2 is the zeroth prime
  totient =: 5&p:
  primeQ =:  1&p:

  NB. first row contains the integer
  NB. second row             totient
  NB. third                  1 iff prime
  (, totient ,: primeQ) >: i. 25

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8 20 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 


  NB. primes first exceeding the limits
  [&.:(p:inv) 10 ^ 2 + i. 4

101 1009 10007 100003 

  p:inv 101 1009 10007 100003

25 168 1229 9592 

  NB. limit and prime count
  (,. p:inv) 10 ^ 2 + i. 5
  100    25
 1000   168
10000  1229

100000 9592 

  1e6 78498

</lang>

Julia

Translation of: Python

<lang julia>φ(n) = sum(1 for k in 1:n if gcd(n, k) == 1)

is_prime(n) = φ(n) == n - 1

function runphitests() 

   for n in 1:25
       println(" φ($n) == $(φ(n))", is_prime(n) ? ", is prime" : "")
   end
   count = 0
   for n in 1:100_000
       count += is_prime(n)
       if n in [100, 1000, 10_000, 100_000]
           println("Primes up to $n: $count")
       end
   end

end

runphitests()

</lang>

Output:


φ(1) == 1
φ(2) == 1, is prime
φ(3) == 2, is prime
φ(4) == 2
φ(5) == 4, is prime
φ(6) == 2
φ(7) == 6, is prime
φ(8) == 4
φ(9) == 6
φ(10) == 4
φ(11) == 10, is prime
φ(12) == 4
φ(13) == 12, is prime
φ(14) == 6
φ(15) == 8
φ(16) == 8
φ(17) == 16, is prime
φ(18) == 6
φ(19) == 18, is prime
φ(20) == 8
φ(21) == 12
φ(22) == 10
φ(23) == 22, is prime
φ(24) == 8
φ(25) == 20
Primes up to 100: 25
Primes up to 1000: 168
Primes up to 10000: 1229
Primes up to 100000: 9592

Kotlin

Translation of: Go

<lang scala>// Version 1.3.21

fun totient(n: Int): Int { 

   var tot = n
   var nn = n
   var i = 2
   while (i * i <= nn) {
       if (nn % i == 0) {
           while (nn % i == 0) nn /= i
           tot -= tot / i
       }
       if (i == 2) i = 1
       i += 2
   }
   if (nn > 1) tot -= tot / nn
   return tot

}

fun main() { 

   println(" n  phi   prime")
   println("---------------")
   var count = 0
   for (n in 1..25) {
       val tot = totient(n)
       val isPrime  = n - 1 == tot
       if (isPrime) count++
       System.out.printf("%2d   %2d   %b\n", n, tot, isPrime)
   }
   println("\nNumber of primes up to 25     = $count")
   for (n in 26..100_000) {
       val tot = totient(n)
       if (tot == n-1) count++
       if (n == 100 || n == 1000 || n % 10_000 == 0) {
           System.out.printf("\nNumber of primes up to %-6d = %d\n", n, count)
       }
   }

}</lang>

Output:
Same as Go example.

Lua

Averages about 7 seconds under LuaJIT <lang lua>-- Return the greatest common denominator of x and y function gcd (x, y) 

 return y == 0 and math.abs(x) or gcd(y, x % y)

end

-- Return the totient number for n function totient (n) 

 local count = 0
 for k = 1, n do
   if gcd(n, k) == 1 then count = count + 1 end
 end
 return count

end

-- Determine (inefficiently) whether p is prime function isPrime (p) 

 return totient(p) == p - 1

end

-- Output totient and primality for the first 25 integers print("n", string.char(237), "prime") print(string.rep("-", 21)) for i = 1, 25 do 

 print(i, totient(i), isPrime(i))

end

-- Count the primes up to 100, 1000 and 10000 local pCount, i, limit = 0, 1 for power = 2, 4 do 

 limit = 10 ^ power
 repeat
   i = i + 1
   if isPrime(i) then pCount = pCount + 1 end
 until i == limit
 print("\nThere are " .. pCount .. " primes below " .. limit)

end</lang>

Output:
n       φ       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

There are 25 primes below 100

There are 168 primes below 1000

There are 1229 primes below 10000

Pascal

Yes, a very slow possibility to check prime <lang pascal>{$IFDEF FPC} 

 {$MODE DELPHI}

{$IFEND} function gcd_mod(u, v: NativeUint): NativeUint;inline; //prerequisites u > v and u,v > 0 

 var
   t: NativeUInt;
 begin
   repeat
     t := u;
     u := v;
     v := t mod v;
   until v = 0;
   gcd_mod := u;
 end;

function Totient(n:NativeUint):NativeUint; var 

 i : NativeUint;

Begin 

 result := 1;
 For i := 2 to n do
   inc(result,ORD(GCD_mod(n,i)=1));

end;

function CheckPrimeTotient(n:NativeUint):Boolean;inline; begin 

 result :=  (Totient(n) = (n-1));

end;

procedure OutCountPrimes(n:NativeUInt); var 

 i,cnt :  NativeUint;

begin 

 cnt := 0;
 For i := 1 to n do
   inc(cnt,Ord(CheckPrimeTotient(i)));
 writeln(n:10,cnt:8);

end;

procedure display(n:NativeUint); var 

 idx,phi : NativeUint;

Begin 

 if n = 0 then
   EXIT;
 writeln('number n':5,'Totient(n)':11,'isprime':8);
 For idx := 1 to n do
 Begin
   phi := Totient(idx);
   writeln(idx:4,phi:10,(phi=(idx-1)):12);
 end

end; var 

 i : NativeUint;

Begin 

 display(25);

 writeln('Limit  primecount');
 i := 100;
 repeat
   OutCountPrimes(i);
   i := i*10;
 until i >100000;

end.</lang>

Output
number n Totient(n) isprime
   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
Limit  primecount
       100      25
      1000     168
     10000    1229
    100000    9592

real  3m39,745s

alternative

changing Totient-funtion in program atop to Computing Euler's totient function on wikipedia, like GO and C.

Impressive speedup.Checking with only primes would be even faster. <lang pascal>function totient(n:NativeUInt):NativeUInt; const 

 //delta of numbers not divisible by 2,3,5 (0_1+6->7+4->11 ..+6->29+2->3_1
 delta : array[0..7] of NativeUint = (6,4,2,4,2,4,6,2);

var 

 i, quot,idx: NativeUint;

Begin 

 // div mod by constant is fast.
 //i = 2
 result := n;
 if (2*2 <= n) then
 Begin
   IF not(ODD(n)) then
   Begin
     // remove numbers with factor 2,4,8,16, ...
     while not(ODD(n)) do
       n := n DIV 2;
     //remove count of multiples of 2
     dec(result,result DIV 2);
   end;
 end;
 //i = 3
 If (3*3 <= n) AND (n mod 3 = 0) then
 Begin
   repeat
     quot := n DIV 3;
     IF n <> quot*3 then
       BREAK
     else
       n := quot;
   until false;
   dec(result,result DIV 3);
 end;
 //i = 5
 If (5*5 <= n) AND (n mod 5 = 0) then
 Begin
   repeat
     quot := n DIV 5;
     IF n <> quot*5 then
       BREAK
     else
       n := quot;
   until false;
   dec(result,result DIV 5);
 end;
 i := 7;
 idx := 1;
 //i = 7,11,13,17,19,23,29, ...49 ..
 while i*i <= n do
 Begin
   quot := n DIV i;
   if n = quot*i then
   Begin
     repeat
       IF n <> quot*i then
         BREAK
       else
         n := quot;
       quot := n DIV i;
     until false;
     dec(result,result DIV i);
   end;
   i := i + delta[idx];
   idx := (idx+1) AND 7;
 end;
 if n> 1 then
   dec(result,result div n);

end;</lang>

Output
number n Totient(n) isprime
   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
Limit  primecount
       100      25
      1000     168
     10000    1229
    100000    9592
   1000000   78498
  10000000  664579

real	0m7,369s

Perl

Direct calculation of 𝜑

Translation of: Perl 6

<lang perl>use utf8; binmode STDOUT, ":utf8";

sub gcd { 

 my ($u, $v) = @_;
 while ($v) {
   ($u, $v) = ($v, $u % $v);
 }
 return abs($u);

}

push @𝜑, 0; for $t (1..10000) { 

   push @𝜑, scalar grep { 1 == gcd($_,$t) } 1..$t;

}

printf "𝜑(%2d) = %3d%s\n", $_, $𝜑[$_], $_ - $𝜑[$_] - 1 ?  : ' Prime' for 1 .. 25; print "\n";

for $limit (100, 1000, 10000) { 

   printf "Count of primes <= $limit: %d\n", scalar grep {$_ == $𝜑[$_] + 1} 0..$limit;

} </lang>

Output:
𝜑( 1) =   1
𝜑( 2) =   1 Prime
𝜑( 3) =   2 Prime
𝜑( 4) =   2
𝜑( 5) =   4 Prime
𝜑( 6) =   2
𝜑( 7) =   6 Prime
𝜑( 8) =   4
𝜑( 9) =   6
𝜑(10) =   4
𝜑(11) =  10 Prime
𝜑(12) =   4
𝜑(13) =  12 Prime
𝜑(14) =   6
𝜑(15) =   8
𝜑(16) =   8
𝜑(17) =  16 Prime
𝜑(18) =   6
𝜑(19) =  18 Prime
𝜑(20) =   8
𝜑(21) =  12
𝜑(22) =  10
𝜑(23) =  22 Prime
𝜑(24) =   8
𝜑(25) =  20

Count of primes <= 100: 25
Count of primes <= 1000: 168
Count of primes <= 10000: 1229

Using 'ntheory' library

Much faster. Output is the same as above.

Library: ntheory

<lang perl>use utf8; binmode STDOUT, ":utf8";

use ntheory qw(euler_phi);

my @𝜑 = euler_phi(0,10000); # Returns list of all values in range

printf "𝜑(%2d) = %3d%s\n", $_, $𝜑[$_], $_ - $𝜑[$_] - 1 ?  : ' Prime' for 1 .. 25; print "\n";

for $limit (100, 1000, 10000) { 

   printf "Count of primes <= $limit: %d\n", scalar grep {$_ == $𝜑[$_] + 1} 0..$limit;

}</lang>

Perl 6

Works with: Rakudo version 2018.11

This is an incredibly inefficient way of finding prime numbers.


<lang perl6>my \𝜑 = 0, |(1..*).hyper(:8degree).map: -> $t { +(^$t).grep: * gcd $t == 1 };

printf "𝜑(%2d) = %3d %s\n", $_, 𝜑[$_], $_ - 𝜑[$_] - 1 ??  !! 'Prime' for 1 .. 25;

(100, 1000, 10000).map: -> $limit { 

   say "\nCount of primes <= $limit: " ~ +(^$limit).grep: {$_ == 𝜑[$_] + 1}

}</lang>

Output:
𝜑( 1) =   1
𝜑( 2) =   1 Prime
𝜑( 3) =   2 Prime
𝜑( 4) =   2
𝜑( 5) =   4 Prime
𝜑( 6) =   2
𝜑( 7) =   6 Prime
𝜑( 8) =   4
𝜑( 9) =   6
𝜑(10) =   4
𝜑(11) =  10 Prime
𝜑(12) =   4
𝜑(13) =  12 Prime
𝜑(14) =   6
𝜑(15) =   8
𝜑(16) =   8
𝜑(17) =  16 Prime
𝜑(18) =   6
𝜑(19) =  18 Prime
𝜑(20) =   8
𝜑(21) =  12
𝜑(22) =  10
𝜑(23) =  22 Prime
𝜑(24) =   8
𝜑(25) =  20

Count of primes <= 100: 25

Count of primes <= 1000: 168

Count of primes <= 10000: 1229

Phix

Translation of: Go

<lang Phix>function totient(integer n) 

   integer tot = n, i = 2
   while i*i<=n do
       if mod(n,i)=0 then
           while true do
               n /= i
               if mod(n,i)!=0 then exit end if
           end while
           tot -= tot/i
       end if
       i += iff(i=2?1:2)
   end while
   if n>1 then
       tot -= tot/n
   end if
   return tot

end function

printf(1," n phi prime\n") printf(1," --------------\n") integer count = 0 for n=1 to 25 do 

   integer tot = totient(n),
           prime = (n-1=tot)
   count += prime
   string isp = iff(prime?"true":"false")
   printf(1,"%2d   %2d   %s\n",{n,tot,isp})

end for printf(1,"\nNumber of primes up to 25 = %d\n",count) for n=26 to 100000 do 

   count += (totient(n)=n-1)
   if find(n,{100,1000,10000,100000}) then
       printf(1,"Number of primes up to %-6d = %d\n",{n,count})
   end if

end for</lang>

Output:
 n  phi   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

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
Number of primes up to 100000 = 9592

PicoLisp

<lang PicoLisp>(gc 32) (de gcd (A B) 

  (until (=0 B)
     (let M (% A B)
        (setq A B B M) ) )
  (abs A) )

(de totient (N) 

  (let C 0
     (for I N
        (and (=1 (gcd N I)) (inc 'C)) )
     (cons C (= C (dec N))) ) )

(de p? (N) 

  (let C 0
     (for A N
        (and
           (cdr (totient A))
           (inc 'C) ) )
     C ) )

(let Fmt (3 7 10) 

  (tab Fmt "N" "Phi" "Prime?")
  (tab Fmt "-" "---" "------")
  (for N 25
     (tab Fmt
        N
        (car (setq @ (totient N)))
        (cdr @) ) ) )

(println 

  (mapcar p? (25 100 1000 10000 100000)) )</lang>
Output:
 N    Phi    Prime?
  -    ---    ------
  1      1
  2      1         T
  3      2         T
  4      2
  5      4         T
  6      2
  7      6         T
  8      4
  9      6
 10      4
 11     10         T
 12      4
 13     12         T
 14      6
 15      8
 16      8
 17     16         T
 18      6
 19     18         T
 20      8
 21     12
 22     10
 23     22         T
 24      8
 25     20
(9 25 168 1229 9592)

Python

<lang python>from math import gcd

def φ(n): 

   return sum(1 for k in range(1, n + 1) if gcd(n, k) == 1)

if __name__ == '__main__': 

   def is_prime(n):
       return φ(n) == n - 1
   
   for n in range(1, 26):
       print(f" φ({n}) == {φ(n)}{', is prime' if is_prime(n)  else }")
   count = 0
   for n in range(1, 10_000 + 1):
       count += is_prime(n)
       if n in {100, 1000, 10_000}:
           print(f"Primes up to {n}: {count}")</lang>
Output:
 φ(1) == 1
 φ(2) == 1, is prime
 φ(3) == 2, is prime
 φ(4) == 2
 φ(5) == 4, is prime
 φ(6) == 2
 φ(7) == 6, is prime
 φ(8) == 4
 φ(9) == 6
 φ(10) == 4
 φ(11) == 10, is prime
 φ(12) == 4
 φ(13) == 12, is prime
 φ(14) == 6
 φ(15) == 8
 φ(16) == 8
 φ(17) == 16, is prime
 φ(18) == 6
 φ(19) == 18, is prime
 φ(20) == 8
 φ(21) == 12
 φ(22) == 10
 φ(23) == 22, is prime
 φ(24) == 8
 φ(25) == 20
Primes up to 100: 25
Primes up to 1000: 168
Primes up to 10000: 1229

REXX

<lang rexx>/*REXX program calculates the totient numbers for a range of numbers, and count primes. */ parse arg N . /*obtain optional argument from the CL.*/ if N== | N=="," then N= 25 /*Not specified? Then use the default.*/ tell= N>0 /*N positive>? Then display them all. */ N= abs(N) /*use the absolute value of N for loop.*/ w= length(N) /*W: is used to aligning the output. */ primes= 0 /*the number of primes found (so far).*/ 

                                                /*if N was negative, only count primes.*/
   do j=1  for  N;     tn= phi(j)               /*obtain totient number for a number.  */
   prime= word('(prime)', 1 +  (tn \== j-1 ) )  /*determine if  J  is a prime number.  */
   if prime\==  then primes= primes+1         /*if a prime, then bump the prime count*/
   if tell  then say 'totient number for '  right(j, w)  " ──► "  right(tn, w) ' ' prime
   end

say say right(primes, w) ' primes detected for numbers up to and including ' N exit /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ gcd: parse arg x,y; do until y==0; parse value x//y y with y x; end /*until*/ 

    return x

/*──────────────────────────────────────────────────────────────────────────────────────*/ phi: procedure; parse arg z; #= z==1 

                     do m=1  for z-1;  if gcd(m, z)==1  then #= # + 1;    end   /*m*/
    return #</lang>
output   when using the default input of:     25 
totient number for   1  ──►   1
totient number for   2  ──►   1   (prime)
totient number for   3  ──►   2   (prime)
totient number for   4  ──►   2
totient number for   5  ──►   4   (prime)
totient number for   6  ──►   2
totient number for   7  ──►   6   (prime)
totient number for   8  ──►   4
totient number for   9  ──►   6
totient number for  10  ──►   4
totient number for  11  ──►  10   (prime)
totient number for  12  ──►   4
totient number for  13  ──►  12   (prime)
totient number for  14  ──►   6
totient number for  15  ──►   8
totient number for  16  ──►   8
totient number for  17  ──►  16   (prime)
totient number for  18  ──►   6
totient number for  19  ──►  18   (prime)
totient number for  20  ──►   8
totient number for  21  ──►  12
totient number for  22  ──►  10
totient number for  23  ──►  22   (prime)
totient number for  24  ──►   8
totient number for  25  ──►  20

 9  primes detected for numbers up to and including  25
output   when using the input of:     -100 
 25  primes detected for numbers up to and including  100
output   when using the input of:     -1000 
 168  primes detected for numbers up to and including  1000
output   when using the input of:     -10000 
 1229  primes detected for numbers up to and including  10000
output   when using the input of:     -1000000 
 9592 primes detected for numbers up to and including  100000

Ruby

<lang ruby> require "prime"

def 𝜑(n) 

 n.prime_division.inject(1) {|res, (pr, exp)| res *= (pr-1) * pr**(exp-1) }

end

1.upto 25 do |n| 

 tot = 𝜑(n)
 puts "#{n}\t #{tot}\t #{"prime" if n-tot==1}"

end

[100, 1_000, 10_000, 100_000].each do |u| 

 puts "Number of primes up to #{u}: #{(1..u).count{|n| n-𝜑(n) == 1} }"

end </lang>

Output:
1	 1	 
2	 1	 prime
3	 2	 prime
4	 2	 
5	 4	 prime
6	 2	 
7	 6	 prime
8	 4	 
9	 6	 
10	 4	 
11	 10	 prime
12	 4	 
13	 12	 prime
14	 6	 
15	 8	 
16	 8	 
17	 16	 prime
18	 6	 
19	 18	 prime
20	 8	 
21	 12	 
22	 10	 
23	 22	 prime
24	 8	 
25	 20	 
Number of primes up to 100: 25
Number of primes up to 1000: 168
Number of primes up to 10000: 1229
Number of primes up to 100000: 9592

Rust

<lang rust>use num::integer::gcd;

fn main() { 

   // Compute the totient of the first 25 natural integers
   println!("N\t phi(n)\t Prime");
   for n in 1..26 {
       let phi_n = phi(n);
       println!("{}\t {}\t {:?}", n, phi_n, phi_n == n - 1);
   }

   // Compute the number of prime numbers for various steps
   [1, 100, 1000, 10000, 100000]
       .windows(2)
       .scan(0, |acc, tuple| {
           *acc += (tuple[0]..=tuple[1]).filter(is_prime).count();
           Some((tuple[1], *acc))
       })
       .for_each(|x| println!("Until {}: {} prime numbers", x.0, x.1));

}

fn is_prime(n: &usize) -> bool { 

   phi(*n) == *n - 1

}

fn phi(n: usize) -> usize { 

   (1..=n).filter(|&x| gcd(n, x) == 1).count()

}</lang>

Output is: 

N	 phi(n)	 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
Until 100: 25 prime numbers
Until 1000: 168 prime numbers
Until 10000: 1229 prime numbers
Until 100000: 9592 prime numbers

Scala

The most concise way to write the totient function in Scala is using a naive lazy list: <lang scala>@tailrec def gcd(a: Int, b: Int): Int = if(b == 0) a else gcd(b, a%b) def totientLaz(num: Int): Int = LazyList.range(2, num).count(gcd(num, _) == 1) + 1</lang>

The above approach, while concise, is not very performant. It must check the GCD with every number between 2 and num, giving it an O(n*log(n)) time complexity. A better solution is to use the product definition of the totient, repeatedly extracting prime factors from num: <lang scala>def totientPrd(num: Int): Int = { 

 @tailrec
 def dTrec(f: Int, n: Int): Int = if(n%f == 0) dTrec(f, n/f) else n
 
 @tailrec
 def tTrec(ac: Int, i: Int, n: Int): Int = if(n != 1){
   if(n%i == 0) tTrec(ac*(i - 1)/i, i + 1, dTrec(i, n))
   else tTrec(ac, i + 1, n)
 }else{
   ac
 }
 
 tTrec(num, 2, num)

}</lang>

This version is significantly faster, but the introduction of multiple recursive methods makes it far less concise. We can, however, embed the recursion into a lazy list to obtain a function as fast as the second example yet almost as concise as the first, at the cost of some readability: <lang scala>@tailrec def scrub(f: Long, num: Long): Long = if(num%f == 0) scrub(f, num/f) else num def totientLazPrd(num: Long): Long = LazyList.iterate((num, 2: Long, num)){case (ac, i, n) => if(n%i == 0) (ac*(i - 1)/i, i + 1, scrub(i, n)) else (ac, i + 1, n)}.find(_._3 == 1).get._1</lang>

To generate the output up to 100000, Longs are necessary.

Output:
1 (Not Prime): 1
2   (Prime)  : 1
3   (Prime)  : 2
4 (Not Prime): 2
5   (Prime)  : 4
6 (Not Prime): 2
7   (Prime)  : 6
8 (Not Prime): 4
9 (Not Prime): 6
10 (Not Prime): 4
11   (Prime)  : 10
12 (Not Prime): 4
13   (Prime)  : 12
14 (Not Prime): 6
15 (Not Prime): 8
16 (Not Prime): 8
17   (Prime)  : 16
18 (Not Prime): 6
19   (Prime)  : 18
20 (Not Prime): 8
21 (Not Prime): 12
22 (Not Prime): 10
23   (Prime)  : 22
24 (Not Prime): 8
25 (Not Prime): 20

Prime Count <= N...
100: 25
1000: 168
10000: 1229
100000: 9592

Sidef

The Euler totient function is built-in as Number.euler_phi(), but we can easily re-implement it using its multiplicative property: phi(p^k) = (p-1)*p^(k-1). <lang ruby>func 𝜑(n) { 

   n.factor_exp.prod {|p|
       (p[0]-1) * p[0]**(p[1]-1)
   }

}</lang>

<lang ruby>for n in (1..25) { 

   var totient = 𝜑(n)
   printf("𝜑(%2s) = %3s%s\n", n, totient, totient==(n-1) ? ' - prime' : )

}</lang>

Output:
𝜑( 1) =   1
𝜑( 2) =   1 - prime
𝜑( 3) =   2 - prime
𝜑( 4) =   2
𝜑( 5) =   4 - prime
𝜑( 6) =   2
𝜑( 7) =   6 - prime
𝜑( 8) =   4
𝜑( 9) =   6
𝜑(10) =   4
𝜑(11) =  10 - prime
𝜑(12) =   4
𝜑(13) =  12 - prime
𝜑(14) =   6
𝜑(15) =   8
𝜑(16) =   8
𝜑(17) =  16 - prime
𝜑(18) =   6
𝜑(19) =  18 - prime
𝜑(20) =   8
𝜑(21) =  12
𝜑(22) =  10
𝜑(23) =  22 - prime
𝜑(24) =   8
𝜑(25) =  20

<lang ruby>[100, 1_000, 10_000, 100_000].each {|limit| 

   var pi = (1..limit -> count_by {|n| 𝜑(n) == (n-1) })
   say "Number of primes <= #{limit}: #{pi}"

}</lang>

Output:
Number of primes <= 100: 25
Number of primes <= 1000: 168
Number of primes <= 10000: 1229
Number of primes <= 100000: 9592

VBA

Translation of: Phix

<lang vb>Private Function totient(ByVal n As Long) As Long 

   Dim tot As Long: tot = n
   Dim i As Long: i = 2
   Do While i * i <= n
       If n Mod i = 0 Then
           Do While True
               n = n \ i
               If n Mod i <> 0 Then Exit Do
           Loop
           tot = tot - tot \ i
       End If
       i = i + IIf(i = 2, 1, 2)
   Loop
   If n > 1 Then
       tot = tot - tot \ n
   End If
   totient = tot

End Function

Public Sub main() 

   Debug.Print " n  phi   prime"
   Debug.Print " --------------"
   Dim count As Long
   Dim tot As Integer, n As Long
   For n = 1 To 25
       tot = totient(n)
       prime = (n - 1 = tot)
       count = count - prime
       Debug.Print Format(n, "@@"); Format(tot, "@@@@@"); Format(prime, "@@@@@@@@")
   Next n
   Debug.Print
   Debug.Print "Number of primes up to 25     = "; Format(count, "@@@@")
   For n = 26 To 100000
       count = count - (totient(n) = n - 1)
       Select Case n
           Case 100, 1000, 10000, 100000
               Debug.Print "Number of primes up to"; n; String$(6 - Len(CStr(n)), " "); "="; Format(count, "@@@@@")
           Case Else
       End Select
   Next n

End Sub</lang>

Output:
 n  phi   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

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
Number of primes up to 100000 = 9592

zkl

<lang zkl>fcn totient(n){ [1..n].reduce('wrap(p,k){ p + (n.gcd(k)==1) }) } fcn isPrime(n){ totient(n)==(n - 1) }</lang> <lang zkl>foreach n in ([1..25]){ 

  println("\u03c6(%2d) ==%3d %s"
     .fmt(n,totient(n),isPrime(n) and "is prime" or ""));

}</lang>

Output:
φ( 1) ==  1 
φ( 2) ==  1 is prime
φ( 3) ==  2 is prime
φ( 4) ==  2 
φ( 5) ==  4 is prime
φ( 6) ==  2 
φ( 7) ==  6 is prime
φ( 8) ==  4 
φ( 9) ==  6 
φ(10) ==  4 
φ(11) == 10 is prime
φ(12) ==  4 
φ(13) == 12 is prime
φ(14) ==  6 
φ(15) ==  8 
φ(16) ==  8 
φ(17) == 16 is prime
φ(18) ==  6 
φ(19) == 18 is prime
φ(20) ==  8 
φ(21) == 12 
φ(22) == 10 
φ(23) == 22 is prime
φ(24) ==  8 
φ(25) == 20

<lang zkl>count:=0; foreach n in ([1..10_000]){ // yes, this is sloooow 

  count+=isPrime(n);
  if(n==100 or n==1000 or n==10_000)
     println("Primes <= %,6d : %,5d".fmt(n,count));

}</lang>

Output:
Primes <=    100 :    25
Primes <=  1,000 :   168
Primes <= 10,000 : 1,229
Retrieved from "https://rosettacode.org/wiki/Totient_function?oldid=286778"