6
\$\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
6
\$\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;
          }
        }
      }
    }
    
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks , i tried it without sieve and got similar results \$\endgroup\$ – Syed Saad Jul 29 '16 at 19:13
0
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$

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.