Project Euler - 06

[Petcheco]

Hello, guys.

This challenge asks us to find the 10001-th prime. Here's my code:

// A reasonable approximation is to say that the n-th prime is such that p(n) = n*(log n + log*(log n) - 1).
// With that in mind, we can say that the 10001-th prime  is smaller than 10100*(log 10100 + log(log 10100) - 1), which we can round to 105000.

#include <iostream>
#include <cmath>

#define MAX_INTERVAL 105000

using namespace std;

int Wanted_Prime = 0;

void Show_Prime(int);

void Show_Prime(int Wanted_Prime)
{
    cout << "The 10001-th prime is " << Wanted_Prime << endl;
}

int main()
{
    bool Is_Prime = true;
    int Number_of_Primes = 1;

    for (int i = 3; i < MAX_INTERVAL; i += 2)
    {
        Is_Prime = true;
        for (int j =2; j <= floor(sqrt(i)); j++)
        {
            if (i % j == 0)
            {
                Is_Prime = false;
            }
        }

        if (Is_Prime == true)
        {
            Number_of_Primes++;
        }
        if (Number_of_Primes == 10001)
        {
            Wanted_Prime = i;
            Show_Prime(Wanted_Prime);
            i = MAX_INTERVAL;
        }
    }

    return 0;
}

It takes 0.300s to run. What can I do to improve it?

Thanks.

Petcheco

[ddanbe]

Change line 28.
Instead of

for (int j =2; j <= floor(sqrt(i)); j++)

use

int EndVal = floor(sqrt(i));
for (int j =2; j <= EndVal; j++)

Now, the functions floor and sqrt are only called once.
Oh and perhaps this

for (int i = 3; i < MAX_INTERVAL; i += 2)
{
  int EndVal = floor(sqrt(i));
  for (int j =2; j <= EndVal; j++)
  {          
    Is_Prime = i % j != 0;        
  }
  ...

could be a further improvement but I'm not sure about that.

[rubberman]

I used to do this all the time when I was researching public key encryption and Goedel algorithms. I would create an array of 10K elements that included all of the primes up to that, using the Sieve of Aratosthenes (I almost always misspell that). Look here for good coverage of the various algorithms to use: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

[Petcheco]

@ddanbe

Thanks for the tips, mate. I don't understand what

Is_Prime = i % j != 0;

is supposed to do. Could you explain?

Thank you.

@rubberman

I'll be sure to take a look on those algorithms. It seems kind of tricky. Should be fun.

Thank you, mate.

Petcheco

[Petcheco]

P.S.: This problem is actually the challenge number 07.

[ddanbe]

Is_Prime = (i % j) != 0;
Lets "dissect" this:
Is_Prime is a boolean.
(i % j) != 0 is a boolean expression that has either a value of true or false, depending on the outcome of the operation i % j.
So this is in total a legitimate statement.
Normally I would advise to do it as in your code, which is much clearer. But here as you want optimization it is allowed. Perhaps put in an explanation comment.

[ddanbe]

Perhaps it is even better to do it this way, using a break statement:

for (int i = 3; i < MAX_INTERVAL; i += 2)
{
  int EndVal = floor(sqrt(i));
  Is_Prime = true;
  for (int j =2; j <= EndVal; j++)
  {   
      if ( i % j == 0 )
      {
        Is_Prime = false; 
        break; //found non prime so leave the loop
      }
  }
  ...

[Petcheco]

Very good, sir. I forgot that we can use break to end a for-loop.

Thank you very much for all your help!

[Petcheco]

Hey, guys.

I improved my code. Could you take a look at it now?

** main.cpp **

// A reasonable approximation is to say that the n-th prime is such that p(n) = n*(log n + log*(log n) - 1).
// With that in mind, we can say that the 10001-th prime  is smaller than 10100*(log 10100 + log(log 10100) - 1), which we can round to 105000.

#include <iostream>
#include <cmath>
#include <vector>

#include "Sieve of Eratosthenes.h"

using namespace std;

void Show_Prime(int);

void Show_Prime(int Wanted_Prime)
{
    cout << "The 10001-th prime is " << Wanted_Prime << endl;
}

int main()
{
            Find_Primes_until_n(Primes);
            Show_Prime(Wanted_Prime);

    return 0;
}

** Sieve of Eratosthenes.h **

#ifndef SIEVE_OF_ERATOSTHENES_H_INCLUDED
#define SIEVE_OF_ERATOSTHENES_H_INCLUDED

#define Upper_Limit 105000

using namespace std;

#define Upper_Limit 105000

typedef unsigned long long int ulli;
ulli Prime_Number = 0;
ulli Wanted_Prime = 0;

vector<bool> Primes;

ulli Find_Primes_until_n (vector<bool>);

ulli Find_Primes_until_n(vector<bool> Primes)
{
    Primes.resize(Upper_Limit);
    fill(Primes.begin(),Primes.begin() + Upper_Limit , true);
    for (ulli i = 2; i < Upper_Limit; i++)
    {
        if(Primes[i])
        {
            Prime_Number++;
        for (ulli j = 2*i; j <Upper_Limit; j+= i)
        {
             Primes[j] = false;
        }
        }
         if (Prime_Number == 10001)
        {
            Wanted_Prime = i;
            break;
        }
     }
     return Wanted_Prime;
}


#endif // SIEVE_OF_ERATOSTHENES_H_INCLUDED

Thank you.

Petcheco

[Petcheco]

Obs.:

void Show_Prime(int);

void Show_Prime(int Wanted_Prime)
{
    cout << "The 10001-th prime is " << Wanted_Prime << endl;
}

should read

void Show_Prime(ulli);

void Show_Prime(ulli Wanted_Prime)
{
    cout << "The 10001-th prime is " << Wanted_Prime << endl;
}