-4

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
}
flashformer
  • 3
  • 3
  • 2
    Perhaps you should ask your classmate (or whomever gave you this code)? – SergeyA Sep 17 '21 at 20:01
  • Unrelated: This is a very inefficient method for generating a list of prime numbers. Seek ye a Prime number sieve. – user4581301 Sep 17 '21 at 20:02
  • 1
    `isprime = trial % primes[i] > 0;` seems pretty important, since its continual persistence as `true` during the limited ascension loop which contains it, ultimately dictates whether `trial` is prime or not. – WhozCraig Sep 17 '21 at 20:04
  • 1
    The loop shouldn't even calculate 9/7. It should stop at 9/3. – Thomas Sablik Sep 17 '21 at 20:05
  • @ThomasSablik what do you mean? when i=3 for loop, the 4th element within the primes array is 7 and trial is 9 ( 3+2 +2 +2). – flashformer Sep 17 '21 at 20:22
  • 1
    *I would like your help to understand how the below code is producing the prime numbers.* -- The debugger, single-stepping through the code, is the best teacher as to why a program behaves the way it does. – PaulMcKenzie Sep 17 '21 at 20:28
  • *what do you mean? when i=3 for loop, the 4th element within the primes array is 7 and trial is 9 ( 3+2 +2 +2)* -- Well, if you know that, what's the issue in figuring out the variable values in the other parts of the code? Or is this just a guess? That's why using a debugger should be done, so it can confirm what you think should be true. – PaulMcKenzie Sep 17 '21 at 20:30
  • @PaulMcKenzie i don't understand how 9/7 is not a prime, it seems that the program skips it for good reason as ( trial 9 can't be prime), but I don't understand how it's actually skipping it within the code. – flashformer Sep 17 '21 at 20:47
  • Put a breakpoint when the test for `9` is done, and see what the values of the variables are. That's the whole point of a debugger. [What is a debugger?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – PaulMcKenzie Sep 17 '21 at 20:49
  • @PaulMcKenzie thanks, i've done it but i still don't understand it..it seems it's resetting i to 0, but can't understand what causes it. – flashformer Sep 17 '21 at 21:19
  • The loop stops with 9/3. `isprime` is set to false and `isprime` is a condition of the loop. 9/7 is never checked – Thomas Sablik Sep 17 '21 at 21:41
  • @flashformer *"what do you mean? when i=3 for loop,"* -- You've ventured into Neverland. When `trial` is `9`, `limit` is `3`, so `primes[2] > limit` and **`i` never becomes `3`**. Sure, it's easy to reach a contradiction when you start with a false premise. *Use diagnostics or a debugger to discover values that are actually obtained by the variables, so you can ask about a real scenario.* – JaMiT Sep 17 '21 at 22:19
  • Thank you guys, I've run it through step by step via the debugger and now it's clear the for loop ensures that every new trial number is checked against lower primes ( starting always with prime [0], incremented after each % test ) up to the square root of the trial numbers. The loops end only if the result of % is false or if the limit is reached ( up to the square root of the trial number). – flashformer Sep 18 '21 at 14:08

1 Answers1

0

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.

Joseph Larson
  • 8,530
  • 1
  • 19
  • 36