CPP Question - Primes array, how the sqrt while loop finds the prime numbers? [closed]-CodePudding

I would like your help to understand how the below code is producing the prime numbers. The code is correct, but I am not sure how the loop ensures that isprime = trial % primes[3] > 0; is not a prime number.

P.s. I know that 9 is not a prime number, but I would like to understand how the below code understands that 9 is not a prime number... probably it's connected to the sqrt and limit?

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

CodePudding user response：

Okay, think about prime numbers. A number is prime if there are no prime numbers that divide into it evenly.

maybe_prime % lower_prime == 0

If that's true for any of the prime numbers lower than your number, then your maybe_prime number isn't prime -- because something else divides easily.

That's a start of understanding. Now, let's talk about the square root.

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

This part is tricky to understand. Let's say our number is NOT prime. That means there exists a prime number < limit for which:

trial / a_number = b_number

and b_number is an integer. That is:

trial % a_number = 0

In other words:

a_number * b_number = trial.

Right?

Let's start with a number with lots of divisors -- like 105.

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

And then:

3 * 5 * 7 = 105

With me?

Consider the pattern:

3 * 35
5 * 21
7 * 15

Now, the square root of 105 is 10.246. But the code above turns this into an integer -- just 10.

You'll notice the pattern above -- it's converging on the square root of 105 -- converging on 10. The first number gets bigger, the second smaller.

It turns out... A number is prime if there are no prime numbers <= its square root that divide evenly.

In other words, all limit is doing is preventing a whole ton of math. If you make it to limit and don't find any primes that divide evenly into trial, then you won't find any if you keep going.

When dealing with primes in computing, this is important to remember. You only have to check values up to the square root of your number. If you don't find any by then, you won't find any.