Some algorithms about judging a prime .

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;

#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

 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;
}

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;
}
}