-3

So, I made this little program. It gives all the correct outputs, but when uploading it to the online judge it throw me away a Time Limited Exceeded. Any ideas on how to make it more efficient?

Here is my code. 

int const MAX = 1000001;  
#include<iostream> 
#include<string>
#include<cmath>

using namespace std;

int main()
{
    int count = 0, array[MAX], a, b, pi = 0;  
    bool end = false;

for(int i = 1; i <= MAX; i++)
{
    count = 0;
    for(int j = 2; j <= sqrt(i); j++)
    {
        if(i % j == 0)
        {
            array[i]=0;
            count++;
            break;
        }
    }
    if(count == 0 && i != 1){
        array[i]=1;
    }
}

do {
    cin >> a >> b;
    pi = 0;
    if ((a == 0) && (b == 0)) {
        end = true;
        break;
    }
    else {
        for (int i = a; i <= b; i++) {
            if (array[i] == 1) {
                pi ++;
            }
        }
        cout << pi << endl;
    }
} while (end == false);
cout << endl;

return 0;
}
randomUser
  • 11
  • 1
  • 2
    Trying to imagine how efficient invoking `sqrt()` on every loop-step is. or assuming the compiler has brains, why you're using a `int` for information that could be held in a `bool`. Finally, I see no code to step-by-multipler. Are you familiar with a [Sieve of Eratosthenes](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)? – WhozCraig Jan 18 '14 at 00:29
  • Does this program take no input? Why not just print a fixed list of primes off the web? – phs Jan 18 '14 at 00:30
  • @phs I'm not trying to print a list of prime numbers, but determine how many of them are in a given range. – randomUser Jan 18 '14 at 00:36
  • @WhozCraig No, I'm not familiar with Sieve of Eratosthenes, but I'll look for it. Thank you! – randomUser Jan 18 '14 at 00:38
  • @WhozCraig definitely he need some kind of prime sieve. but he might prefer the `Sieve of Atkin` which is supposedly an optimized version of the `Sieve of Eratosthenes` (see [Sieve of Atkin](http://en.wikipedia.org/wiki/Sieve_of_Atkin)) – James Jan 18 '14 at 00:38
  • @James Sure, thats another. I prefer an SoE when the task really isn't mission critical just for its simplicity. One way or another though, something besides a single-stepping brute-force scan, to be sure. At least the high side is `sqrt()` limited already, so he's to that going for 'em. – WhozCraig Jan 18 '14 at 00:54
  • @James FYI, I'm a she, not a he. And thank you both for your comments. I think I might go this time with the SoE, as WhozCraig said, it is simple. – randomUser Jan 18 '14 at 01:04
  • @randomUser apologies, me and my assumptions :/ – James Jan 18 '14 at 13:38
  • use ["offset" sieve of Eratosthenes](http://stackoverflow.com/a/9557173/849891) (see also [pseudocode](http://stackoverflow.com/a/19641049/849891) and [some discussion](http://stackoverflow.com/a/20762980/849891)). forget about Atkin's, it's too complex to implement and only pays off for producing many millions of primes, reportedly. – Will Ness Jan 19 '14 at 09:05

1 Answers1

1

You may consider using Sieve of Eratosthenes. It is an efficient prime generation algorithm.

invisal
  • 11,075
  • 4
  • 33
  • 54