Largest prime factor: Difference between revisions

Content added Content deleted

Inline

Revision as of 20:36, 2 November 2021

Task

The task description is taken for Project Euler (https://projecteuler.net/problem=3)
What is the largest prime factor of the number 600851475143 ?

ALGOL 68

Based on the Wren and Go samples. <lang algol68>BEGIN # find the largest prime factor of a number #

   # returns the largest prime factor of n #
   PROC max prime factor = ( LONG INT n )LONG INT:
        IF   n < 2
        THEN 1
        ELSE
            LONG INT max factor := n;
            # even factors - only 2 is prime #
            LONG INT v := n;
            WHILE NOT ODD v DO
                max factor := 2;
                v OVERAB 2
            OD;
            # odd factors #
            LONG INT k := 3;
            LONG INT root n = ENTIER long sqrt( n );
            WHILE k <= root n AND v > 1 DO
                WHILE v MOD k = 0 AND v > 1 DO
                    max factor := k;
                    v OVERAB k
                OD;
                k +:= 2
            OD;
            IF v > 1 THEN v ELSE max factor FI
       FI # max prime factor # ;
   # test the max prime factor routine #
   PROC test = ( LONG INT n )VOID:
        print( ( "Largest prime factor of ", whole( n, 0 ), " is ", whole( max prime factor( n ), 0 ), newline ) );
   # test cases #
   test( 600 851 475 143 );
   test(           6 008 );
   test(             751 )

END</lang>

Output:

Largest prime factor of 600851475143 is 6857
Largest prime factor of 6008 is 751
Largest prime factor of 751 is 751

BASIC

GW-BASIC

No primality testing is even required. <lang gwbasic>10 N#=600851475143# 20 J#=3 30 IF J#=N# THEN GOTO 100 40 IF INT(N#/J#) = N#/J# THEN N# = N#/J# 50 J#=J#+2 60 GOTO 30 100 PRINT N#</lang>

Output:

Go

Translation of: Wren

<lang go>package main

import "fmt"

func largestPrimeFactor(n uint64) uint64 {

   if n < 2 {
       return 1
   }
   inc := [8]uint64{4, 2, 4, 2, 4, 6, 2, 6}
   max := uint64(1)
   for n%2 == 0 {
       max = 2
       n /= 2
   }
   for n%3 == 0 {
       max = 3
       n /= 3
   }
   for n%5 == 0 {
       max = 5
       n /= 5
   }
   k := uint64(7)
   i := 0
   for k*k <= n {
       if n%k == 0 {
           max = k
           n /= k
       } else {
           k += inc[i]
           i = (i + 1) % 8
       }
   }
   if n > 1 {
       return n
   }
   return max

}

func main() {

   n := uint64(600851475143)
   fmt.Println("The largest prime factor of", n, "is", largestPrimeFactor(n), "\b.")

}</lang>

Output:

The largest prime factor of 600851475143 is 6857.

Julia

<lang julia> using Primes

@show first(last(factor(600851475143).pe))

</lang>

Output:

first(last((factor(600851475143)).pe)) = 6857

PARI/GP

<lang parigp>A=factor(600851475143) print(A[matsize(A)[1],1])</lang>

Output:

PL/I

Based on the Wren, Go and Algol 68 samples. <lang pli>/* find the largest prime factor of 600851475143 */ largestPrimeFactor: procedure options( main );

   declare ( n, maxFactor, v, k, rootN ) decimal( 12 )fixed;
   n         = 600851475143;
   maxFactor = 1;
   /* even factors */
   v         = n;
   do while( mod( v, 2 ) = 0 );
       maxFactor = 2;
       v = v / 2;
   end;
   /* odd factors */
   k     = 3;
   rootN = sqrt( n );
   do while( k <= rootN & v > 1 );
       do while( mod( v, k ) = 0 & v > 1 );
           maxFactor = k;
           v = v / k;
       end;
       k = k + 2;
   end;
   if v > 1 then maxFactor = v;
   put skip list( 'Largest prime factor of ', n, ' is ', maxFactor );

end largestPrimeFactor;</lang>

Output:

Largest prime factor of     600851475143  is             6857

<lang ring> load "stdlib.ring" see "working..." + nl see "The largest prime factor of the number 600851475143 is:" + nl num = 600851475143 numSqrt = sqrt(num) numSqrt = floor(numSqrt) if numSqrt%2 = 0

  numSqrt++

ok

for n = numSqrt to 3 step -2

   if isprime(n) and num%n = 0
      exit
   ok

Output:

working...
The largest prime factor of the number 600851475143 is:
6857
done...

Wren

Without using any library functions at all (it's a one-liner otherwise): <lang ecmascript>var largestPrimeFactor = Fn.new { |n|

   if (!n.isInteger || n < 2) return 1
   var inc = [4, 2, 4, 2, 4, 6, 2, 6]
   var max = 1
   while (n%2 == 0) {
      max = 2
      n = (n/2).floor
   }
   while (n%3 == 0) {
       max = 3
       n = (n/3).floor
   }
   while (n%5 == 0) {
       max = 5
       n = (n/5).floor
   }
   var k = 7
   var i = 0
   while (k * k <= n) {
       if (n%k == 0) {
           max = k
           n = (n/k).floor
       } else {
           k = k + inc[i]
           i = (i + 1) % 8
       }
   }
   return (n > 1) ? n : max

}

var n = 600851475143 System.print("The largest prime factor of %(n) is %(largestPrimeFactor.call(n)).")</lang>

Output:

The largest prime factor of 600851475143 is 6857.

XPL0

<lang XPL0>real Num, Max, Div, Quot; [Num:= 600851475143.; Max:= 0.; Div:= 2.; repeat loop [Quot:= Num / Div;

               if Mod(Quot, 1.) < 1E-10 then \evenly divisible
                       [Num:= Quot;
                       Max:= Div;
                       ]
               else    quit;
               if Div > Num then quit;
               ];
       Div:= Div + 1.;

until Div > Num; Format(1, 0); RlOut(0, Max); ]</lang>

Output:

Largest prime factor: Difference between revisions

Revision as of 20:36, 2 November 2021

ALGOL 68

BASIC

FreeBASIC

GW-BASIC

C

Fermat

Go

Julia

PARI/GP

PL/I

Raku

Not particularly fast

Particularly fast

Ring

Wren

XPL0