5
\$\begingroup\$

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;

 }
\$\endgroup\$
  • \$\begingroup\$ It causes stack overflow on windows, VC++14. \$\endgroup\$ – Incomputable Jul 29 '16 at 16:45
  • \$\begingroup\$ I used code blocks ,windows and it worked all right. \$\endgroup\$ – Syed Saad Jul 29 '16 at 18:25
  • \$\begingroup\$ I'm not saying the code is broken, just saying that on VC++14 it might fail. \$\endgroup\$ – Incomputable Jul 29 '16 at 18:31
5
\$\begingroup\$
  • 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;
          }
        }
      }
    }
    
\$\endgroup\$
  • \$\begingroup\$ Thanks , i tried it without sieve and got similar results \$\endgroup\$ – Syed Saad Jul 29 '16 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.