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.
//includes
#include <iostream>
//namespace
using namespace std;
//forward declaration
void primes(int n);
//MAIN FUNCTION
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
primes(n);
//pause console
system("pause");
//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
else
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;
continue;
} 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)
continue;
} else {
//move to next divisor
threshold = (currentNumber/currentDivisor)+1;
currentDivisor++;
}
}
}
|
