Prime01
[ Home ] [ Up ]

// file:   prime01.cpp
// date:   08/26/2002
// author: AOUS

#include <iostream.h>

/*
Problem:
  Write a function to check if a given number
  is a prime number.  The function takes an 
  integer and returns true or false.  The name
  of the function is isPrime1().
Examples:
  Here are the first few prime numbers:

  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, 101, 103, 107, 109, 113, 
  127, 131, 137, 139, 149, 151, 157, 163, 
  167, 173, 179, 181, 191, 193, 197, 199, etc.
  http://www.mathforum.org/dr.math/faq/faq.prime.num.html

  A prime number is a positive integer that has 
  exactly two positive integer factors, 1 and 
  itself. For example, if we list the factors 
  of 28, we have 1, 2, 4, 7, 14, and 28. 
  That's six factors. If we list the factors 
  of 29, we only have 1 and 29. That's 2. 
  So we say that 29 is a prime number, but 
  28 isn't. 
  Another way of saying this is that a prime 
  number is a whole number that is not the 
  product of two smaller numbers.


Algorithm1:
  if n is 1 return false
  if n is 2 return true
  if n is divisible by i=2 to n-1 then 
      return false
    else
      return true
  end algorithm


Algorithm2:
  if n is 1 return false
  if n is 2 return true

  for i=2 to n-1 do
    if n%i == 0 then
      return false
    end for

  return true
  end algorithm

Prototype:
  bool isPrime1(int n)

*/

bool isPrime1(int n)
  {
  if (n == 1) return false;
  if (n == 2) return true;

  for (int i=2; i<=n-1; i++)
    {
    if (n%i == 0) 
      return false;
    }

  return true;
  }

void main(void)
  {
  if (isPrime1(15)) cout << "Prime\n"; else cout << "composite\n";
  }