Project Euler – Problem 3

Problem 3 of Project Euler is a computational beast. Nothing more. The problem, as stated on the website is:

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

What is the largest prime factor of the number 600851475143 ?

General Algorithm

Before we start, we have to take a few things into account:

  1. 600851475143 is an insanely large number. Languages like C/C++ have no native support for big integers. Luckily for us, we can store this in a long long unsigned int.
  2. While testing for primes, the following information must be kept in mind:
  3. While the definition of prime numbers is known to most, the second point is rather important. It implies that we need only to check for factors of a number till √n and not till n.

The algorithm is as follows:

  1. Initialise const long long unsigned int n = 600851475143.
  2.  Iterate i through every integer from √n to 1.
  3. If i perfectly divides n, then:
    • If i is prime then the highest factor is i
    • If i is not prime, then check if n/i is prime. If n/i  is prime, then n/i is the highest factor.
    • If neither i nor n/i  is prime, then continue through the loop
  1. Break the loop.

Solution in C++ 

Advertisements
Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: