c++ - 使用平方根计算质数和算法构建查询

Question

下面是素数的计算。我试图解构它以更好地理解循环。此外，我想调整此函数以通过将数字与其平方根进行比较而不是这种方式来查找素数:

(假设在 int main 之前进行了适当的声明)

//判断数是否为质数

bool isPrime (long n)
{
    int a;

    if (n == 1)
    {
        return false;
    }

    for (a = 2; a <= (n / 2); a++)
    {
        if ((n % a) == 0)
        {
            return false;
        }

    }
    return true;
}

但是，观察这个循环，我有一个问题，看看我是否正确地开始观察这个函数。据我所知，它看起来像 int a; 是计数器，它从 2 开始，因为 0 和 1 不是质数。 n 应该是正式变量。它指出，对于除以二时小于或等于自身的每个数字，如果余数大于零，则返回 bool 值 true。同时，如果一个数被 2 整除(因此没有余数)，则它不被视为质数( bool 返回 false)。那个听起来是对的吗？如果没有，请让我知道我在哪里转错了。如果我做对了，请进入程序的后半部分。

现在，primeCount; 在 main 中受 primeCount (2, 50000); 限制，但第一个函数输入此处:

//使用 isPrime 函数对素数进行计数和整理

long primeCount (long x, long y)
{
    bool prime;
    int b;
    int c = 1000;
    int counter = 0;
    int totalSum = 0;

    for (b = 1; b <= y; b++)
    {
        prime = isPrime (b);

        if (prime == true)
        {
            counter++;
        }
        if (b == c)
        {
            cout << setw(10) << left << (b - 999) << setw(10) << left << b << setw(12) << counter << endl;
            cout << fixed << showpoint << setprecision(2) << endl;
            totalSum = totalSum + counter;
            counter = 0;
            c = c + 1000;
        }
    }

现在，我认为 x 和 y 是形式变量，但我不知道 x 应该代表什么。它代表 int c; 吗？该函数中的 for 循环完全让我感到困惑。我不明白。任何可以阐明的信息都将不胜感激。

至于求平方根，我需要使用 3 个嵌套的 for 循环才能得到素数吗？像这样:

 for (a > m => b)

  for (a==m => b==m)

    for (a < m => b>m)

用这种方式定位素数会比这里说明的方式更复杂还是更简单？我知道这需要解决很多问题。如果你们建议我把它分成不同的帖子，我会编辑这个并将后半部分发布在不同的帖子中。感谢您的协助!只是一个新手 C++ 程序员，试图从这些东西中弄清楚 :)

Answer 1

第一个函数isPrime()做它应该做的事。如果数字是素数则返回 true，否则返回 false。循环变量a的原因只运行到 n/2是因为任何数字 n不能有大于 n/2 的因子(除了它本身)。例子？ 6 -- 1, 2, 3 and 6 , 12 -- 1, 2, 3, 4, 6 and 12 .循环只是想看看是否 a有任何因素(将其除而不留余数的数字)。如果是，则它不是质数 (return false)，否则它是 (return true)。

但是我觉得primeCount()没有完全按照预期的方式进行。

来自primeCount()的定义我认为这是为了计算来自 x 的素数总数至 y (在你的情况下是 2 到 50000，因为你提到了 main() 调用 primeCount(2, 50000) )。但是要做到这一点 for循环必须改成这个

for (b = x; b <= y; b++)

变量的作用c这里是检查循环变量的每千分之一的值 b .

注意第一次运行时 b = 1000即b == c该程序打印到目前为止它遇到的素数数量 ( counter )。之后 counter重置为 0和 c现在是2000 .然后，b从 1001 继续至 2000同样的事情重复直到b是 50000。

总的来说，这个想法是从2打印每1000个自然数中存在的素数。至 50000 .