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

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;

}

• It causes stack overflow on windows, VC++14. Commented Jul 29, 2016 at 16:45
• I used code blocks ,windows and it worked all right. Commented Jul 29, 2016 at 18:25
• I'm not saying the code is broken, just saying that on VC++14 it might fail. Commented Jul 29, 2016 at 18:31

• 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;
}
}
}
}

• Thanks , i tried it without sieve and got similar results Commented Jul 29, 2016 at 19:13

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.