Prime Numbers

Demonstration of obtaining prime numbers.

Download it here

A prime number is defined as a number which is not divisible by any number other
than 1 and itself. Given that definition we can develop a method of finding prime
numbers by simply dividing the number in question by every number between 1 and
itself. If any of those numbers divide evenly into the number in question then the
number is not a prime number; otherwise the number is prime.

The processing time of finding primes using an algorithm with the description above is
very hefty (especially when searching for large quantities of primes) because it tests
every number with every other number. However, because 2 divides evenly into all even
numbers, we can cut the time of finding primes in half by only testing odd numbers
(beyond 2) for primality.

Further observations show more potential reduction of processing time for this program.
Because we are checking all odd numbers for primality and there are no prime numbers
which end in 5 (save for 5 itself), we are checking one unnecessary number for every five
we check. This amounts to a great deal of unecessary numbers when we are searching for a
large quantity of primes.

Additionally, factors always work in pairs. The smallest and largest possible factors
are always 2 and exactly half of a number. Therefore, there cannot possibly be any
factors greater than half of a number. So the processing time can be further reduced
by not checking for factors once the potential divisor has reached greater than half
of the potential prime. In fact, this rings true for every additional non-factor integer
incrementing from 2. For example, If neither 2 nor 3 are factors of a number, there are
no factors greater than the number divided by 3. Therefore, we can greatly reduce the
quantity of potential divisors by setting a threshold at x = p/n wher p is the potential
prime number and n is the greatest non-factor integer tested in sequence.

Let's look at some code that finds the first n prime numbers.

#include <iostream>

using namespace std;

//forward declaration
void primes(int n);

int main(){
     //int for user input
     int n;

     //prompt user for input
     cout << "How many prime numbers do you want to find? ";
     cin >> n;

     //find prime numbers

     //pause console

     //end program
     return 0;

//Prime Numbers
//finds the first Nth prime numbers
void primes(int n){
     //numbers to test for primality and to test with
     int currentNumber = 2;
     int currentDivisor = 2;
     int threshold = currentNumber/currentDivisor;

     //loop to find the primes
     while(n >= 0){
         if(currentDivisor == currentNumber || currentDivisor >= threshold){
             //currentNumber is prime, print it to console
             cout << currentNumber << " ";
             n--; //one less prime to find

             //2 is the ONLY even prime number
             if(currentNumber == 2)
                 currentNumber++; //get to 3
                 currentNumber += 2; //get to next odd number

             //do not check numbers which end in 5
             if(currentNumber > 5 && currentNumber%5 == 0)
                 currentNumber += 2;

             currentDivisor = 3; //set to 3 (not checking even numbers)
             threshold = (currentNumber/currentDivisor)+1;

         } else if((currentNumber % currentDivisor) == 0){
             //currentNumber is not a prime
             currentNumber += 2; //move on to next number
             if(currentNumber > 5 && currentNumber%5 == 0)
                 currentNumber += 2;
             currentDivisor = 3; //set to 3 (not checking even numbers)

         } else {
             //move to next divisor
             threshold = (currentNumber/currentDivisor)+1;