CPP 问题 - 素数数组，sqrt while 循环如何找到素数？

Question

我需要你的帮助来理解下面的代码是如何产生质数的。代码是正确的，但我不确定循环如何确保 isprime = trial % primes[3] > 0;不是素数。

P.s。我知道 9 不是质数，但我想了解以下代码如何理解 9 不是质数...可能它与 sqrt 和极限有关？

// Calculating primes using dynamic memory allocation
#include <iostream>
#include <iomanip>
#include <cmath>                                             // For square root function

int main()
{
  size_t max {};                                             // Number of primes required

  std::cout << "How many primes would you like? ";
  std::cin >> max;                                           // Read number required
  
  if (max == 0) return 0;                                    // Zero primes: do nothing
  
  auto* primes {new unsigned[max]};                          // Allocate memory for max primes

  size_t count {1};                                          // Count of primes found
  primes[0] = 2;                                             // Insert first seed prime
  
  unsigned trial {3};                                        // Initial candidate prime
  
  while (count < max)
  {
    bool isprime {true};                                     // Indicates when a prime is found

    const auto limit = static_cast<unsigned>(std::sqrt(trial));
    for (size_t i {}; primes[i] <= limit && isprime; ++i)
    {
      isprime = trial % primes[i] > 0;                       // False for exact division
    }

    if (isprime)                                             // We got one...
      primes[count++] = trial;                               // ...so save it in primes array

    trial += 2;                                              // Next value for checking
  }

 
 // Output primes 10 to a line 
  


for (size_t i{}; i < max; ++i)
  {
    std::cout << std::setw(10) << primes[i];
    if ((i + 1) % 10 == 0)                                   // After every 10th prime...
      std::cout << std::endl;                                // ...start a new line
  }
  std::cout << std::endl;
  
  delete[] primes;                                           // Free up memory...
  primes = nullptr;                                          // ... and reset the pointer
}

Answer 1

好的，想想素数。一个数是质数，如果没有质数可以平分它。

maybe_prime % lower_prime == 0

如果任何比你的数字小的素数都是这样，那么你的 maybe_prime 数字就不是素数——因为其他东西很容易相除。

这是理解的开始。现在，我们来谈谈平方根。

const auto limit = static_cast<unsigned>(std::sqrt(trial));

这部分很难理解。假设我们的数字不是质数。这意味着存在一个质数 < 限制：

trial / a_number = b_number

和b_number是一个整数。即：

trial % a_number = 0

换句话说：

a_number * b_number = trial.

对吗？

让我们从一个有很多除数的数字开始——比如 105。

105 / 3 = 35
105 / 5 = 21
105 / 7 = 15

然后：

3 * 5 * 7 = 105

和我一起？

考虑模式：

3 * 35
5 * 21
7 * 15

现在，105 的平方根是 10.246。但是上面的代码把它变成了一个整数——只有 10.

您会注意到上面的模式 -- 它收敛于 105 的平方根 -- 收敛于 10。第一个数字变大，第二个变小。

事实证明...如果没有质数<=它的平方根，则该数是质数。整除。

换句话说，limit 所做的就是阻止大量的数学运算。如果你到了极限，没有找到平分试验的素数，那么你继续下去，你也找不到。

在计算中处理质数时，记住这一点很重要。您只需检查不超过数字平方根的值。到时候找不到就找不到了。

CPP 问题 - 素数数组，sqrt while 循环如何找到素数？

CPP Question - Primes array, how the sqrt while loop finds the prime numbers?

c++

arrays

algorithm

primes