C++研究

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 常兴龙 阅读(1303) 评论(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为素数
若N 通过一次测试,则N 不是素数的概率为 25%,若N 通过t 次测试,则N 不是
素数的概率为1/4**t。事实上取t 为5 时,N 不是素数的概率为 1/128,N 为素数的
概率已经大于99.99%。
在实际应用中,可首先用300—500个小素数对N 进行测试,以提高拉宾米勒测试
通过的概率,从而提高测试速度。而在生成随机素数时,选取的随机数最好让 r=0,
则可省去步骤(3) 的测试,进一步提高测试速度
  回复  更多评论
  

# re: Some algorithms about judging a prime . 2009-05-16 19:29 u2u
@我们一起来提高
现在最快的是AKS...  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


> hi的博客