Реализация счетчика простых чисел

Question

По какой-то причине мое последнее простое (int prime) не появляется в конце. Любая подсказка? fyi: primeEval обозначает флаг, если концы цикла & & primeEval == 2, число фактически является простым числом. qty означает количество подсчитанных чисел.

int main(){ 


long primeEval=0,prime=0,qtyprime=0; 

time_t timerr=(time(NULL)+10); 



    for (int i = 2; time(NULL)!=timerr; i++) { 

     for (int j = 1; j <= i; j++) { 

      if((i%j)==0 && primeEval<2){ 

       primeEval++; 

       if (i==j && primeEval==2) { 
        qtyprime++; 
        prime=i; 
        primeEval=0; // Resets for the next number 'i' 

       } 
      } 

     } 
    } 

cout << "last prime found: " << prime << endl << "Ttal primes found: " << qtyprime; 
} 

Answer 1

Новый Ответ:

С изменением кода вы теперь будет перебрать все числа. Проблема с этим в настоящее время является то, что как только вы найдете нон простое число, вы никогда не сбросит primeEval и из-за того, что вы никогда не захватит еще простое число Если вы измените код на следующий он будет работать

int main() 
{ 
    long primeEval = 0, prime = 0, qtyprime = 0; 
    time_t timerr = (time(NULL) + 10); 

    for (int i = 2; time(NULL) != timerr; i++) { 

     for (int j = 1; j <= i; j++) { 

      if ((i%j) == 0){ 
       primeEval++; // incmrent factor 
      } 
      // if we are at the end and have 2 factors then we are prime 
      if (i == j && primeEval == 2) { 
       qtyprime++; 
       prime = i; 
       primeEval = 0; // Resets for the next number 'i' 
      } 
      // if we reach the end with more than 2 factors reset and go to the next number 
      if (i == j && primeEval > 2) { 
       primeEval = 0; // Resets for the next number 'i' 
      } 
     } 
    } 
    cout << "last prime found: " << prime << endl << "Ttal primes found: " << qtyprime; 
    cin.get(); 
    return 0; 
} 

Я бы также предложите посмотреть на Which is the fastest algorithm to find prime numbers?, чтобы найти более эффективные способы получения простых чисел.

Старый Ответ:

В коде у вас есть:

for (int i = 2; time(NULL)!=timerr; i=+2) 

Итак, когда вы начинаете проверять от простых чисел вы начинаете с 2, который является простым. Затем вы увеличиваете i на 2, поэтому следующее число, которое вы проверяете, равно 4, что является четным числом. Все четные номера не первичны за 2. исключением Поскольку вы всегда добавляете 2 вы всегда будете иметь четное число, так что только простое число, вы найдете это 2.

Answer 2

У вас есть различные вопросы:

for (int i = 2; time(NULL)!=timerr; i=+2) { 

Здесь синтаксис просто неверен: он должен быть i+=2, а не i=+2, иначе вы будете продолжать устанавливать i на +2 и проверять, является ли 2 простым.

Затем, как указывали другие, почему вы увеличиваете i на 2? Если вы хотите оптимизировать поиск, вы должны увеличить j на 2, а не i! И j должен в любом случае начинаться с 2 (или, учитывая ваш подход, от 1), а затем вы должны попробовать j = 3, а затем вы можете увеличить j на 2 без риска пропустить некоторые важные делители.

Затем вы обнуляете primeEval на 0, только если вы найдете штрих. Если вы проверите номер i, который не является простым, primeEval останется в 2, и вы больше никогда не попадете в блок.

Таким образом, окончательный код может быть:

#include <iostream> 
using namespace std; 

int main(){ 

    long primeEval=0,prime=0,qtyprime=0; 

    time_t timerr=(time(NULL)+10); 

    for (int i = 2; time(NULL)!=timerr; i++) { 
     primeEval=0; 
     for (int j = 1; j <= i; j++) { 
      if((i%j)==0 && primeEval<2){ 
       primeEval++; 
       if (i==j && primeEval==2) { 
        qtyprime++; 
        prime=i; 
        primeEval=0; // Resets for the next number 'i' 
       } 
      } 
     } 
    } 

    cout << "last prime found: " << prime << endl << "Ttal primes found: " << qtyprime; 
}