EulerProject Mathematical and Programming Problems (Answer + Analysis) #3

in #programming7 years ago

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

Leonhard_Euler.jpg

Let us first admire this brilliant portrait of the man himself!


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 <stdio.h> // Include for printf
#include <stdbool.h> // Include for boolean type
#include <math.h> // 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:

Screen Shot 2017-07-18 at 19.37.35.png

As you can see, the answer was indeed correct!

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

Sort:  

Hi, I'd like to include a link to this article in the next math-trail magazine. I hope that's fine with you.

!-=o0o=-!

To follow curated math content follow @math-trail.
If you wish @math-trail to follow you then read this article.
Click here for Mathematics forum on chainBB

I would be honoured! Thank you so much :)

Congratulations! This post has been upvoted from the communal account, @minnowsupport, by Mormegil from the Minnow Support Project. It's a witness project run by aggroed, ausbitbank, teamsteem, theprophet0, and someguy123. The goal is to help Steemit grow by supporting Minnows and creating a social network. Please find us in the Peace, Abundance, and Liberty Network (PALnet) Discord Channel. It's a completely public and open space to all members of the Steemit community who voluntarily choose to be there.

If you like what we're doing please upvote this comment so we can continue to build the community account that's supporting all members.

This post has received a 1.83 % upvote from @booster thanks to: @banjo.