Home > Project Euler > Project Euler Problem 3

Project Euler Problem 3

October 6th, 2009 Dallas Leave a comment Go to 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: ,
  1. Daniel
    October 6th, 2009 at 16:58 | #1
    Reply | Quote

    Hey, your blog is beautiful. But, you should checkout this code highlighter. It’s the best I have found: http://wordpress.org/extend/plugins/wp-syntax/screenshots/

    Euler!

  2. Dallas
    October 6th, 2009 at 18:59 | #2
    Reply | Quote

    @Daniel
    Done.

    e: Ouch, it looks like it mangles some of the symbols. Gotta find a fix…
    e: It appears to happen when I switch to visual mode. It’s not WP-Syntax it’s the built in editor.
    e: Yup, internet confirms it, it is the editor.
    e: Ok, an additional plugin fixed that issue. When I paste code into the editor it still ignores my spacing. That’s becoming more annoying as these get longer.

  3. Jaime Torres
    October 7th, 2009 at 21:59 | #3
    Reply | Quote

    Dumb question… but why didn’t you divide by two, and work your way backwards? Wouldn’t that be significantly faster?

  1. No trackbacks yet.