Today I shall be giving the solution to the third EulerProject problem and explaining the ins and outs of the solution. Without further ado, let us begin :)
The Problem
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
This is one of those problems that can be done easily through methods such as brute force but with a little mathematical knowledge can be computed with minimal processing power. My solution isn't the prettiest but it's more efficient than simple brute force for multiple reasons. To illustrate these, I must first present my solution.
The Solution
To solve this solution in a more efficient fashion I have made use of the Sieve of Eratosthenes algorithm, which allows me to pre-generate all prime numbers up to a given number.
The pseudocode for the algorithm is as follows:
Input: an integer n > 1.
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.for i = 2, 3, 4, ..., not exceeding √n: if A[i] is true: for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n: A[j] := false.Output: all i such that A[i] is true.
I will now present my own implementation of this in my solution:
#include // Include for printf
#include // Include for boolean type
#include // Include for sqrt()
#define VALUE 600851475143
bool *sieve(long);
int main(){
bool *primes = sieve(VALUE);
long largestPrime = 0L;
for(long i = 0; i < VALUE; ++i){
if(primes[i] == true && i > largestPrime){
largestPrime = i;
}
}
printf("%ld\n", largestPrime);
return 0;
}
bool *sieve(long n){
bool A[n];
for(long i = 0; i < n; ++i){
A[i] = true;
}
A[0] = false;
A[1] = false;
for(long i = 2; i < sqrt(n); ++i){
if(A[i] == true){
for(long j = i * i; j < n; j += i){
A[j] = false;
}
}
}
bool *array = A;
return array;
}
As you can see, the algorithm is implemented in the function bool *sieve(long n). What this does is return a pointer to an array containing all prime numbers beneath a given number, which is 600851475143 in this case. Which numbers are primes and which numbers are determined by:
Iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2.
This means each number found to have more than two divisors (i.e 1 and itself) is marked to be not prime. Thereafter, the numbers left unmarked must therefore be prime.
Although this solution certainly wasn't the prettiest that could've been done, it was superior to simple brute force by means of checking a value being iterated over and over against a separate isPrime() function.
The Answer
The number that this solution outputs is 6857 and after inputting this into the EulerProject website I received the following response:
That is all for today, folks, I have you have found this at least somewhat useful. The next problem shall be uploaded hopefully either tomorrow or within the next few days :)
Links
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
https://projecteuler.net/problem=3