Exercise 3-2 (Prime numbers)

Chapter_3     Exercise_3-1     Charlist

Menu     Exercise_3-3

---

---

Exercise 3-2     TCP1, p. 226

Exercose 3-2. Write a program that uses two nested for() loops and the modulus operator (%) to detect and print prime numbers (integral numbers that are not evenly divisible by any other numbers except for themselves and 1).

Primes.cpp         download

#include <iostream>
using std::cout;
using std::endl;

#define SIZE 100 // search for (and print) primes within 2..100

int main()
{
int max = SIZE/2; // max no of primes <= SIZE/2 for SIZE > 7
if (SIZE < 2) {return 1;} // end program, signalling error
if (SIZE <= 7) {max++;}
int primes[max]; // prime numbers found
int np = 0; // no of primes found so far
bool isPrime; // true if a number is prime
int half; // check if n is divisible by primes <= n/2 or sqrt(n)

primes[np++] = 2; // smallest and single even prime

for (int n = 3; n <= SIZE; n += 2)// check only odd numbers
{
isPrime = true; // (re)set
half = n / 2;
// we check odd numbers: n % primes[0] != 0
for (int i = 1; i < np && primes[i] <= half; i++)
{ // Test primality by successive division (modulo):
if (n % primes[i] == 0)
{
isPrime = false; // not prime
break; // out of inner for()
}
}

if (isPrime) // if (isPrime == true)
{
primes[np++] = n;
}
}

for (int i = 0; i < np-1; i++)
{
cout << primes[i] << ',' << ((i % 10 == 9) ? '\n' : ' ');
}
cout << primes[np-1] << endl;

return 0;
}
/*
g++ Primes.cpp -o Primes
./Primes
2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97
*/

Notes:

See also primes.c on the blog Advanced_Linux_Programming, Chapter_4, Sec. 4.1.
Change the SIZE if you want to print more or less prime_numbers. Compare against the list_of_primes on Wikipedia.

---

---

Chapter_3     Exercise_3-1     Charlist

BACK_TO_TOP

Menu     Exercise_3-3