实现质数计数器

Question

出于某种原因，我的最后一个素数 (int prime) 没有出现在最后。任何线索？ fyi：primeEval代表一个flag，如果循环结束&& 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;
}

实现质数计数器

Implementing a prime number counter

c++

algorithm

math

primes