## 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

### 19 Responses to “Project Euler Problem 3”

1. Graham said

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

```> (factors 2)
(2 1)
> (factors 4)
(2 2 1)
> (factors 8)
(2 2 2 1)
> (factors 10)
(2 5)
```
2. Graham said

Python:

```def factors(n):
fs = []
while (n & 1 == 0):
fs.append(2)
n //= 2
f = 3
while n >= f * f:
if (n % f == 0):
fs.append(f)
n //= f
else:
f += 1
if n != 1:
fs.append(n)
return fs
```

Huzzah for native big integers!

3. programmingpraxis said

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.

4. DGel said

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..

``` ```

``` 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 26 27 func Factors(n *big.Int) (answer vector.Vector) { var f, q, r, incr, zero, tmp big.Int f.SetInt64(2) incr.SetInt64(2) for n.Bit(0) == 0 { answer.Push(new(big.Int).Set(&f)) n.Div(n,&f) } f.SetInt64(3) for tmp.Mul(&f,&f).Cmp(n) < 1 { q.DivMod(n, &f, &r) if r.Cmp(&zero) > 0 { f.Add(&f, &incr) } else { n.Set(&q) answer.Push(new(big.Int).Set(&f)) } } if n.Cmp(new(big.Int).SetInt64(1)) != 0 { answer.Push(new(big.Int).Set(n)) } return } ```

5. DGel said

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

6. slabounty said

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

```def prime_factors(n)
fs = []
while n % 2 == 0
fs << 2
n /= 2
end

f = 3
while n >= f**2
if n % f == 0
fs << f
n /= f
else
f += 1
end
end
fs << n if n != 1
fs
end
```

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

7. Phil said

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

Source

8. Mike said

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.

```from itertools import accumulate, chain, cycle

def genfactors(n):
for f in accumulate(chain((2,1,2,2), cycle((4,2,4,2,4,6,2,6)))):
if f*f > n:
break

while not n % f:
yield f
n //= f

if n > 1:
yield n

#some tests
print(list(genfactors(440190069936)))
# -> [2, 2, 2, 2, 3, 317, 3803, 7607]

```

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

9. Graham said

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.

10. programmingpraxis said

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

11. Phil G said

C# version

```	public class Euler3
{
public static long[] PrimeFactors(long n)
{
//			1. Create a list of factors, initially empty.
var factors = new List<long>();

//			2. If n is even, add 2 to the end of the list of factors, divide n by 2, and go to Step 2.
while( (n & 1) == 0)
n /= 2;

//			3. Set f ← 3.
long f = 3;

while(true)
{
//				4. Calculate the quotient q and remainder r when dividing n by f, so that n = q f + r with 0 ≤ r < f.
long q = n / f;
long r = n - q * f;

//				5. If r > 0, set f ← f + 2 and go to Step 4.
if ( r > 0 )
{
f += 2;
}
else
{
//					6. Otherwise, r = 0. Add f to the end of the list of factors. Set n ← q.
n = q;

//					7. If n < f2, add n to the end of the list of factors, output the list of factors, and stop.
if(n < f * f)
{
break;
}
}
}

return factors.ToArray();
}

public static void Main(string[] args)
{
var x1 = 13195;
var fx1 = PrimeFactors(x1);
Console.WriteLine("Prime factors of '{0}' = [{1}]", x1, String.Join(", ", fx1));

var x2 = 600851475143;
var fx2 = PrimeFactors(x2);
Console.WriteLine("Prime factors of '{0}' = [{1}]", x2, String.Join(", ", fx2));
Console.WriteLine("Largest prime factor = {0}", fx2[fx2.Length - 1]);
}
}
```
12. Green said

in c language

#include
int main()
{
long long int n = 600851475143;
long long int a;
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;
}

13. David said

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.)

```: deven?  ( d -- ? )
drop  1 and  0= ;

: d/mod  ( d n -- d/n d%n )
locals| n |
\ FORTH does not have remainder function for double division
\ so we multiply the quotient by the divisor and subtract...
\
2dup  1 n  M*/   2dup 2>r   \ get quotient & save a copy
n 1 M*/ d- drop             \ compute remainder
2r> ;                       \ restore quotient

: .factors ( d -- )
BEGIN 2dup deven? >r  2. 2over d<  r> and WHILE
2 .  d2/
REPEAT

3 locals| f |
BEGIN  2dup  f dup m*  d< not WHILE
2dup f d/mod  rot 0= IF
f .
2nip      \ drop n; quotient on stack replaces it
ELSE
2drop     \ drop quotient
f 2 +  TO f
THEN
REPEAT
d. ;
```

Testing:

```13,195 .factors 5 7 13 29  ok
1,472,991,001 .factors 23 359 178393  ok
178393 359 m* 23 1 m*/ d. 1472991001  ok
8, .factors 2 2 2  ok
```

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!”);

15. RandomlyGenerated said

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));

}

}

16. RandomlyGenerated said

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));

}

}

17. annie said

I have done its very easy and convenient solution. Check this out here @ http://crispylogs.com/project-euler-problem-3-solution/