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

Re: Project Euler - 06 80 80

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.

Re: Project Euler - 06 80 80

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

Re: Project Euler - 06 80 80

@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

Re: Project Euler - 06 80 80

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

Re: Project Euler - 06 80 80

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.

Re: Project Euler - 06 80 80

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
      }
  }
  ...
Re: Project Euler - 06 80 80

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

Thank you very much for all your help!

Re: Project Euler - 06 80 80

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

Re: Project Euler - 06 80 80

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;
}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.19 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.