## Project Euler Problem 3

### September 20, 2011

Here’s our solution:

`(define (factors n) ; trial division`

(let loop ((n n) (fs '()))

(if (even? n) (loop (/ n 2) (cons 2 fs))

(let loop ((n n) (f 3) (fs fs))

(if (< n (* f f)) (reverse (cons n fs))

(if (zero? (modulo n f))

(loop (/ n f) f (cons f fs))

(loop n (+ f 2) fs)))))))

And here’s a sample run:

`> (factors 13195)`

(5 7 13 29)

You can run the program at http://programmingpraxis.codepad.org/9NbfghJq.

Pages: 1 2

It looks like this may not behave well for powers of two, though it handles other evens fine:

Python:

Huzzah for native big integers!

How embarrassing! I need a step 2.5 that reads “If

n= 1, output the list of factors and stop.” and make the corresponding change in the function.Trying to learn Google Go, first time using big.Int

Have to say that I don’t find it very intuitive to use, but then again, I’m only just starting..

Oh, sorry for the cruft.. used an online syntax highlighter, but doesn’t appear that it worked very well.

In ruby (pretty much exactly the same as Graham’s python version) …

You could also monkey patch Integer to provide this in a more ruby like way.

In Python. Slightly more verbose, and with the steps interspersed through the code as comments. I’m gradually getting the hang of Python.

Source

Same problem solved in C# language

https://sites.google.com/site/eulerproblemsincsharp/home/problem-3

Here’s a slight twist on the described function. Rather than try all

odd numbers >= 3, I used a 30-wheel to generate the possible factors.

Also, the function is a generator which returns successive factors of its

argument. Use list() to get the last factor.

@graham/@slabounty – I think line 12/14 should be f += 2, so that f skips even numbers.

Thanks for catching that, @Mike; I could have sworn I put in += 2. Anyway, nice wheel! I’ll have to read up on wheel factorization and Python3′s accumulate.

Graham, you can read about wheel factorization at the earlier exercise at Programming Praxis.

C# version

in c language

#include

int main()

{

long long int n = 600851475143;

long long int a[100];

long long int i,f,q,r,j;

i=0;

while(n%2==0)

{

a[i] = 2;

i++;

n=n/2;

}

f=3;

while(n > (f*f))

{

q = n/f;

r = n%f;

if(r>0)

{

f = f+2;

}

else

{

a[i] = f;

i++;

n = q;

if(n < (f*f))

{

a[i] = n;

i++;

}

}

}

for(j=0; j<i; ++j)

printf("%lld ",a[j]);

printf("\n");

return 0;

}

FORTH Version to find greatest prime factor. Rather than factor all even numbers, the first step factors all even numbers > 2. When n is equal to 2, the square test fails, so the odd factoring loop does not execute. Therefore there is no special case to check for n = 1 at the end, but more importantly the invariant is preserved that when the function ends, the greatest prime factor is on the stack as a 64 bit integer. (If the final “d.” and printing is removed, the FORTH word would become a function to return the largest prime factor.)

Testing:

C#:

long num = 600851475143;

long f = 1;

long z = 1;

while (z != num)

{

if (num % f == 0)

{

Console.WriteLine(f);

z = z * f;

}

f++;

}

Console.WriteLine(“DONE!”);

Console.ReadLine();

In Java:

public class LargestPrimeFactor {

private static double primefactor(double n) {

double i=2;

for(;itemp)? i:temp;

}

}

return i;

}

public static void main(String[] args) {

System.out.println(primefactor(600851475143.0));

}

}

HMM the above code was cut off

public class LargestPrimeFactor {

private static double primefactor(double n) {

double i=2;

for(;itemp)? i:temp;

}

}

return i;

}

public static void main(String[] args) {

System.out.println(primefactor(600851475143.0));

}

}