Сколько простых чисел между заданным диапазоном? C++

Question

Итак, я сделал эту небольшую программу. Он дает все правильные выходы, но при загрузке его в онлайн-судью он меня отбрасывает Time Limited Exceeded. Любые идеи о том, как сделать его более эффективным?

Вот мой код.

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

Answer 1

Вы можете использовать Sieve of Eratosthenes. Это эффективный алгоритм простого генерации.