1.GRIDDLE METHOD (ALSO CALLED SIFT METHOD)
When I was a student in Bachelor phrase , a teacher has tought me a method called griddle method , it's principle is:
if a number can be devided by another number(except 1) , it isn't a prime , so , we set the non-prime at zero. after all number [In fact , half of the range checked is OK ]test finished , We simply output the NON-ZERO number , it 's the prime table in the RANGE.
E.G
Define the Range from 1-100;
/********************************************************************
created: 2007/04/19
created: 19:4:2007 3:00
filename: C:\testvc6\TestStll\TestStll.cpp
file path: C:\testvc6\TestStll
file base: TestStll
file ext: cpp
author: Chang xinglong(King.C)
purpose: Print Prime Table in RANGE(1-100)
*********************************************************************/
The Code Here :
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
void InitArray(int A[] ,int len)
{
for (int i=0;i<len;i++)
{
A[i]=i+1;
}
}
void OutputPrime(int A[] ,int len)
{
for (int i=2;i<len;i++)
{
for (int j=2;i*j<=len;j++)
{
A[i*j-1]=0;
cout<<i<<","<<j<<","<<i*j<<endl;
}
}
for (i=0;i<len;i++)
{
if (A[i]!=0)
{
cout<<A[i]<<" ";
}
}
cout<<endl;
}
// Main Method [4/19/2007 Changxinglong (King.C)]
int main(int argc, char* argv[])
{
int A[100];
InitArray(A,100);
OutputPrime(A,100);
return 1;
}
2.THE DIRECT METHOD
E.G
/********************************************************************
created: 2007/04/19
created: 19:4:2007 3:00
filename: C:\testvc6\TestStll\TestStll.cpp
file path: C:\testvc6\TestStll
file base: TestStll
file ext: cpp
author: Chang xinglong(King.C)
purpose: Prime ?
*********************************************************************/
Here is the Kernel Function(Quote :
STL TURORIAL REFERRENCE):
1//predicate, which returns whether an integer is a prime number
2bool isPrime (int number)
3{
4//ignore negative sign
5number = abs(number);
6// 0 and 1 are prime numbers
7if (number == 0 || number == 1) {
8return true;
9}
10//find divisor that divides without a remainder
11int divisor;
12for (divisor = number/2; number%divisor != 0; --divisor) {
13;
14}
15//if no divisor greater than 1 is found, it is a prime number
16return divisor == 1;
17}
In Main Function , traverse the given range judge every number use the above function:
int main(int argc , char * argv[])
{
int A[100];
InitArray(A,100);
for(int i=0;i<100;i++)
if(isPrime(A[i]))
cout<<A[i]<<endl;
}
3. Extention
Further , if there is a given List or Vector and it's filled with data , how can you find the prime number in the data effiectly ?
STL Algorithm can help you indeed. After the step two , we can write a few code to implement the function:
int main()
{
list<int> coll;
//insert elements from 1 to 100
for (int i=1; i<=100; ++i) {
coll.push_back(i);
}
//search for prime number
list<int>::iterator pos;
pos = find_if (coll.begin(), coll.end(), //range
isPrime); //predicate
if (pos != coll.end()) {
//found
cout << *pos << " is first prime number found" << endl;
}
else {
//not found
cout << "no prime number found" << endl;
}
}