Archive

Posts Tagged ‘problem 3’

Project Euler Problem 3

October 6th, 2009 Dallas 3 comments

This one was actually a little bit of a challenge.  My first attempt got the right answer, but took about 3 hours to do so.  After consulting some online resources (my girlfriend), and rediscovering prime factorization I rewrote  the program.  Now it takes under a second to solve the puzzle.

I thought this was interesting: if you search “prime factor of 600851475143” on Wolfram Alpha it gives you all of the factorizations, including the answer.

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace Project_Euler_3
{
 class Program
 {
  static void Main(string[] args)
  {
   new Program();
  }
 
  Program()
  {
   ulong compositeValue = 600851475143;
   ulong compositeFactor = compositeValue;
   bool isDone = false;
 
   while (!isDone)
   {
    ulong prime = getNextPrime();
 
    while (compositeFactor % prime != 0)
     prime = getNextPrime(prime);
 
    compositeFactor /= prime;
 
    if (isPrimeValue(compositeFactor))
     isDone = true;
   }
 
   Console.WriteLine(compositeFactor);
   Console.ReadKey();
  }
 
  ulong getNextPrime()
  {
   return getNextPrime(0);
  }
 
  ulong getNextPrime(ulong value)
  {
   ulong nextPossiblePrime = value + 1;
 
   for (; !isPrimeValue(nextPossiblePrime); nextPossiblePrime++) ;
 
   return nextPossiblePrime;
  }
 
  bool isPrimeValue(ulong value)
  {
   for (ulong i = 1; i <= (ulong)Math.Ceiling(Math.Sqrt(value)); i++)
   {
    if (value == 1)
     return false;
    if (i == value)
     return true;
    else if (value % i == 0 && i != 1)
     return false;
   }
 
   return true;
  }
 }
}
Categories: Project Euler Tags: ,