0

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

3
Contributors
9
Replies
28
Views
2 Years
Discussion Span
Last Post by Petcheco
0

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.

Edited by ddanbe: addition

0

@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

0

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.

1

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
      }
  }
  ...
0

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

Thank you very much for all your help!

0

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

Edited by Petcheco

0

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;
}
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.