Find the 10001st prime number (in C++)

Question

I wrote this solution for project Euler #7, to find the 10001th prime number using sieve of eratosthenes. It's really slow though. Any suggestions to improve performance (without using more complex sieves like sieve of atkin)?

#include<iostream>
#include<bits/stdc++.h>
#include<climits>
#define max 500000
using namespace  std;


int main()
{
 int ctr = 0;
 int i=2,j,n=10001,p=2;
 int arr[max];
 memset(arr,0,sizeof(arr));
 while(1)
 {

 p=2;
 while(p*p<=i)
 {

  if(arr[p] == 0)
     for(j=p*p;j<=i;j+=p)
        arr[j] = 1;

        p++;

    }
   if(arr[i]==0)
    ctr++;
   if(ctr==n)
    break;
   i++;

  }

 cout<<i;

 }

Answer 1

• Why is everybody using #include<bits/stdc++.h>? It is so hard to include <cstring> to get memset working?
• Why do you need <climits>?
• Don't use using namespace std;. It's a bad practice.
• Static array of ints with size 500000 is likely too big to fit into stack. Use int * arr = new int[max] and delete [] arr; instead.
• Using whole integers to store boolean value is just a waste of memory.

• It takes 42 seconds to find result. My version (without sieve) takes about real: 0.015s, user: 0.013s.

  #include <iostream>
  
  bool isPrime(int num) {
    for (int i = 2; i*i <= num; ++i) {
      if ((num % i) == 0) return false;
    }
    return num > 1;
  }
  
  int main() {
    int i = 2;
    for (int primes = 0; ; ++i) {
      if (isPrime(i)) {
        if (++primes == 10001) {
          std::cout << i << "\n";
          break;
        }
      }
    }
  }
  

Answer 2

If the prime number to be found is always going to be the 10001st prime number, then you can greatly improve the performance by hard-coding the result:

#include <iostream>
#define PRIME_10001 104743

int main(void)
{
    std::cout << PRIME_10001 << '\n';
    return 0;
}

If 104743 is banned for some reason, here are some alternatives:

• 0x19927 in base 16,
• 0314447 in octal,
• 0b11001100100100111 in binary with C++14 (or GNU C),
• 104'743 with a C++14 digit separator

If you do use the for-loop approach mentioned in the previous answer, you should note that the condition of this loop may overflow:

for (int i = 2; i*i <= num /* for i as little as 256: kaboom! */; ++i) {

Instead, using division eliminates several possibilities:

for (int i = 2; i <= num/i; ++i) {

You should probably use an unsigned integer to remove the rest of the possibilities for overflow. Alternatively, check if num is negative and return false if it is.