# C++研究

Ｃ++细节深度探索及软件工程

C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
 37 随笔 :: 0 文章 :: 74 评论 :: 0 Trackbacks

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

}

posted on 2007-04-19 03:05 常兴龙 阅读(1280) 评论(8)  编辑 收藏 引用 所属分类: Algorithm

### 评论

# re: Some algorithms about judging a prime . 2007-04-19 10:58 uglystone
Write well!
I think tha IsPrime funtion shoule be implemented as a functors!
it may be more elegant!
class IsPrime{
public:
IsPrime(){
}
bool isPrime (int number)
{
.....
}
};  回复  更多评论

# re: Some algorithms about judging a prime . 2007-04-19 22:18 chenger

# re: Some algorithms about judging a prime . 2007-04-26 19:00 oyjpart

# re: Some algorithms about judging a prime . 2007-05-12 23:26 不是很懂
A primality test is a test to determine whether or not a given number is prime, as opposed to actually decomposing the number into its constituent prime factors (which is known as prime factorization).

Primality tests come in two varieties: deterministic and probabilistic. Deterministic tests determine with absolute certainty whether a number is prime. Examples of deterministic tests include the Lucas-Lehmer test and elliptic curve primality proving. Probabilistic tests can potentially (although with very small probability) falsely identify a composite number as prime (although not vice versa). However, they are in general much faster than deterministic tests. Numbers that have passed a probabilistic prime test are therefore properly referred to as probable primes until their primality can be demonstrated deterministically.

A number that passes a probabilistic test but is in fact composite is known as a pseudoprime. There are many specific types of pseudoprimes, the most common being the Fermat pseudoprimes, which are composites that nonetheless satisfy Fermat's little theorem.

The Rabin-Miller strong pseudoprime test is a particularly efficient test. Mathematica versions 2.2 and later have implemented the multiple Rabin-Miller test in bases 2 and 3 combined with a Lucas pseudoprime test as the primality test used by the function PrimeQ[n]. Like many such algorithms, it is a probabilistic test using pseudoprimes. In order to guarantee primality, a much slower deterministic algorithm must be used. However, no numbers are actually known that pass advanced probabilistic tests (such as Rabin-Miller) yet are actually composite.

The state of the art in deterministic primality testing for arbitrary numbers is elliptic curve primality proving. As of 2004, the program PRIMO can certify a 4769-digit prime in approximately 2000 hours of computation (or nearly three months of uninterrupted computation) on a 1 GHz processor using this technique.

Unlike prime factorization, primality testing was long believed to be a P-problem (Wagon 1991). This had not been demonstrated, however, until Agrawal et al. (2002) unexpectedly discovered a polynomial time algorithm for primality testing that has asymptotic complexity of (Bernstein 2002, Clark 2002, Indian Institute of Technology 2002, Pomerance 2002ab, Robinson 2002). Their algorithm has come to be called the AKS primality test.

http://mathworld.wolfram.com/PrimalityTest.html  回复  更多评论

# re: Some algorithms about judging a prime . 2007-05-17 00:12 天津大学计算机学院 常兴龙
Very appreciated for your comment , I have benefited a lot from it. thanks again!  回复  更多评论

# re: Some algorithms about judging a prime . 2008-04-24 02:01 Rex.Kingsir
Thanks a lot for talk so much!  回复  更多评论

# re: Some algorithms about judging a prime . 2008-07-05 16:45 我们一起来提高

（1）计算奇数M，使得N=(2**r)*M+1
（2）选择随机数A<N
（3）对于任意i<r，若A**((2**i)*M) MOD N = N-1，则N通过随机数A的测试
（4）或者，若A**M MOD N = 1，则N通过随机数A的测试
（5）让A取不同的值对N进行5次测试，若全部通过则判定N为素数

回复  更多评论

# re: Some algorithms about judging a prime . 2009-05-16 19:29 u2u
@我们一起来提高