Generating prime numbers-CodePudding

I have started learning C language recently, but since I've first stumbled upon prime number generators I've been having trouble understanding the code. to be clear i do know what prime numbers are, i just would like someone to explain to me what happens in the code. here is an example from a book that im studying.

#include <stdio.h>
#include <stdbool.h>

int main(void) {

    int p, i, primes[50], primeIndex = 2;
    bool isPrime;

    primes[0] = 2;
    primes[1] = 3;

    for (p = 5; p <= 50; p = p   2) {
        isPrime = true;

        // this is the part that I'm having trouble with 
        for (i = 1; isPrime && p / primes[i] >= primes[i];   i)
            if (p % primes[i] == 0)
                isPrime = false;

        if (isPrime == true) {
           primes[primeIndex] = p;
             primeIndex;
        }
        //--------------------
    }

    for (i = 0; i < primeIndex;   i)
        printf("%i ", primes[i]);

    printf("\n");

    return 0;
}

I've been scratching my head for quite some time by now and i can't get through this one on my own, I would be glad if someone could help.

CodePudding user response：

To determine if p is prime, the loop iterates on the array of primes found so far, checking if p modulo primes[i] is 0, which indicates that p is a multiple of primes[i]. If so isPrime is set to false and the loop stops at the next iteration because the test isPrime && p / primes[i] >= primes[i] will be false.

The reason for the second part of the test, p / primes[i] >= primes[i], is to stop the loop once all prime numbers less or equal to the square root of p have been tested.

Here is an alternate version with a simpler test and a break statement:

       isPrime = true;

       for (i = 1; p / primes[i] >= primes[i];   i) {
            if (p % primes[i] == 0) {
                isPrime = false;
                break;
            }
       }

       // here isPrime is true if and only if p is a prime number.

Note that the primes[] array has been initialized with 2 and 3, so 5 will be proven a prime immediately because 5 / primes[1] = 5 / 3 = 1, which is smaller than 3.

Note also that only even numbers are tested from 5 up and i starts at 1, skipping the modulo operation by 2, which will obviously evaluate to 1.

Finally, p is only tested up to 50, which makes the array of 50 primes amply sufficient: only 23 values are tested in the loop (odd numbers from 5 to 49) so at most 25 values could potentially be set in primes[].