# 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. – Incomputable Jul 29 '16 at 16:45
• I used code blocks ,windows and it worked all right. – Syed Saad Jul 29 '16 at 18:25
• I'm not saying the code is broken, just saying that on VC++14 it might fail. – Incomputable Jul 29 '16 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 – Syed Saad Jul 29 '16 at 19:13