Programming in C

Defining an Array 105

the term “previously generated” should trigger in your mind the idea that an array must
be involved here.You can use an array to store each prime number as it is generated.
As a further optimization of the prime number generator program, it can be readily
demonstrated that any nonprime integer nmust have as one of its factors an integer that
is less than or equal to the square root of n.This means that it is only necessary to deter-
mine if a given integer is prime by testing it for even divisibility against all prime factors
up to the square root of the integer.
Program 7.4 incorporates the previous discussions into a program to generate all
prime numbers up to 50.

Program 7.4 Revising the Program to Generate Prime Numbers,Version 2

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

// Modified program to generate prime numbers

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;

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