Which is the fastest algorithm to find prime numbe

问题:

Which is the fastest algorithm to find out prime numbers using C++? I have used sieve\'s algorithm but I still want it to be faster!

回答1:

A very fast implementation of the Sieve of Atkin is Dan Bernstein\'s primegen. This sieve is more efficient than the Sieve of Eratosthenes. His page has some benchmark information.

回答2:

If it has to be really fast you can include a list of primes:
http://www.bigprimes.net/archive/prime/

If you just have to know if a certain number is a prime number, there are various prime tests listed on wikipedia. They are probably the fastest method to determine if large numbers are primes, especially because they can tell you if a number is not a prime.

回答3:

He, he I know I\'m a question necromancer replying to old questions, but I\'ve just found this question searching the net for ways to implement efficient prime numbers tests.

Until now, I believe that the fastest prime number testing algorithm is Strong Probable Prime (SPRP). I am quoting from Nvidia CUDA forums:

One of the more practical niche problems in number theory has to do with identification of prime numbers. Given N, how can you efficiently determine if it is prime or not? This is not just a thoeretical problem, it may be a real one needed in code, perhaps when you need to dynamically find a prime hash table size within certain ranges. If N is something on the order of 2^30, do you really want to do 30000 division tests to search for any factors? Obviously not.

The common practical solution to this problem is a simple test called an Euler probable prime test, and a more powerful generalization called a Strong Probable Prime (SPRP). This is a test that for an integer N can probabilistically classify it as prime or not, and repeated tests can increase the correctness probability. The slow part of the test itself mostly involves computing a value similar to A^(N-1) modulo N. Anyone implementing RSA public-key encryption variants has used this algorithm. It\'s useful both for huge integers (like 512 bits) as well as normal 32 or 64 bit ints.

The test can be changed from a probabilistic rejection into a definitive proof of primality by precomputing certain test input parameters which are known to always succeed for ranges of N. Unfortunately the discovery of these \"best known tests\" is effectively a search of a huge (in fact infinite) domain. In 1980, a first list of useful tests was created by Carl Pomerance (famous for being the one to factor RSA-129 with his Quadratic Seive algorithm.) Later Jaeschke improved the results significantly in 1993. In 2004, Zhang and Tang improved the theory and limits of the search domain. Greathouse and Livingstone have released the most modern results until now on the web, at http://math.crg4.com/primes.html, the best results of a huge search domain.

See here for more info: http://primes.utm.edu/prove/prove2_3.html and http://forums.nvidia.com/index.php?showtopic=70483

If you just need a way to generate very big prime numbers and don\'t care to generate all prime numbers < an integer n, you can use Lucas-Lehmer test to verify Mersenne prime numbers. A Mersenne prime number is in the form of 2^p -1. I think that Lucas-Lehmer test is the fastest algorithm discovered for Mersenne prime numbers.

And if you not only want to use the fastest algorithm but also the fastest hardware, try to implement it using Nvidia CUDA, write a kernel for CUDA and run it on GPU.

You can even earn some money if you discover large enough prime numbers, EFF is giving prizes from $50K to $250K: https://www.eff.org/awards/coop

回答4:

There is a 100% mathematical test that will check if a number P is prime or composite, called AKS Primality Test.

The concept is simple: given a number P, if all the coefficients of (x-1)^P - (x^P-1) are divisible by P, then P is a prime number, otherwise it is a composite number.

For instance, given P = 3, would give the polynomial:

   (x-1)^3 - (x^3 - 1)
 = x^3 + 3x^2 - 3x - 1 - (x^3 - 1)
 = 3x^2 - 3x

And the coefficients are both divisible by 3, therefore the number is prime.

And example where P = 4, which is NOT a prime would yield:

   (x-1)^4 - (x^4-1)
 = x^4 - 4x^3 + 6x^2 - 4x + 1 - (x^4 - 1)
 = -4x^3 + 6x^2 - 4x

And here we can see that the coefficients 6 is not divisible by 4, therefore it is NOT prime.

The polynomial (x-1)^P will P+1 terms and can be found using combination. So, this test will run in O(n) runtime, so I don\'t know how useful this would be since you can simply iterate over i from 0 to p and test for the remainder.

回答5:

Is your problem to decide whether a particular number is prime? Then you need a primality test (easy). Or do you need all primes up to a given number? In that case prime sieves are good (easy, but require memory). Or do you need the prime factors of a number? This would require factorization (difficult for large numbers if you really want the most efficient methods). How large are the numbers you are looking at? 16 bits? 32 bits? bigger?

One clever and efficient way is to pre-compute tables of primes and keep them in a file using a bit-level encoding. The file is considered one long bit vector whereas bit n represents integer n. If n is prime, its bit is set to one and to zero otherwise. Lookup is very fast (you compute the byte offset and a bit mask) and does not require loading the file in memory.

回答6:

It depends on your application. There are some considerations:

• Do you need just the information whether a few numbers are prime, do you need all prime numbers up to a certain limit, or do you need (potentially) all prime numbers?
• How big are the numbers you have to deal with?

The Miller-Rabin and analogue tests are only faster than a sieve for numbers over a certain size (somewhere around a few million, I believe). Below that, using a trial division (if you just have a few numbers) or a sieve is faster.

回答7:

Rabin-Miller is a standard probabilistic primality test. (you run it K times and the input number is either definitely composite, or it is probably prime with probability of error 4^-K. (a few hundred iterations and it\'s almost certainly telling you the truth)

There is a non-probabilistic (deterministic) variant of Rabin Miller.

The Great Internet Mersenne Prime Search (GIMPS) which has found the world\'s record for largest proven prime (2^74,207,281 - 1 as of June 2017), uses several algorithms, but these are primes in special forms. However the GIMPS page above does include some general deterministic primality tests. They appear to indicate that which algorithm is \"fastest\" depends upon the size of the number to be tested. If your number fits in 64 bits then you probably shouldn\'t use a method intended to work on primes of several million digits.

回答8:

I will let you decide if it\'s the fastest or not.

using System;
namespace PrimeNumbers
{

public static class Program
{
    static int primesCount = 0;


    public static void Main()
    {
        DateTime startingTime = DateTime.Now;

        RangePrime(1,1000000);   

        DateTime endingTime = DateTime.Now;

        TimeSpan span = endingTime - startingTime;

        Console.WriteLine(\"span = {0}\", span.TotalSeconds);

    }


    public static void RangePrime(int start, int end)
    {
        for (int i = start; i != end+1; i++)
        {
            bool isPrime = IsPrime(i);
            if(isPrime)
            {
                primesCount++;
                Console.WriteLine(\"number = {0}\", i);
            }
        }
        Console.WriteLine(\"primes count = {0}\",primesCount);
    }



    public static bool IsPrime(int ToCheck)
    {

        if (ToCheck == 2) return true;
        if (ToCheck < 2) return false;


        if (IsOdd(ToCheck))
        {
            for (int i = 3; i <= (ToCheck / 3); i += 2)
            {
                if (ToCheck % i == 0) return false;
            }
            return true;
        }
        else return false; // even numbers(excluding 2) are composite
    }

    public static bool IsOdd(int ToCheck)
    {
        return ((ToCheck % 2 != 0) ? true : false);
    }
}
}

It takes approximately 82 seconds to find and print prime numbers within a range of 1 to 1,000,000, on my Core 2 Duo laptop with a 2.40 GHz processor. And it found 78,498 prime numbers.

回答9:

I don\'t know about any predefined algorithm but I created my own which is very fast. It can process 20 digits numbers in less than 1 seconds. The max capability of this program is 18446744073709551615. The program is :

#include <iostream>
#include <cmath>
#include <stdlib.h>

using namespace std;

unsigned long long int num = 0;

bool prime(){
if(num % 2 == 0 || num == 1){
    return false;
}

unsigned long int square_root = sqrt(num);
for(unsigned long int i = 3;i <= square_root;i += 2){
    if(num % i == 0){
        return false;
    }
}

return true;
}

int main()
{
do{
    system(\"cls\");
cout << \"Enter number : \";
cin >> num;

if(prime()){
    cout<<\"The number is a prime number\"<<endl<<endl<<endl<<endl;
}else{
    cout<<\"The number is not a prime number\"<<endl<<endl<<endl<<endl;
}
system(\"pause\");
}while(1);

return 0;
}

回答10:

I always use this method for calculating primes numbers following with the sieve algorithm.

void primelist()
 {
   for(int i = 4; i < pr; i += 2) mark[ i ] = false;
   for(int i = 3; i < pr; i += 2) mark[ i ] = true; mark[ 2 ] = true;
   for(int i = 3, sq = sqrt( pr ); i < sq; i += 2)
       if(mark[ i ])
          for(int j = i << 1; j < pr; j += i) mark[ j ] = false;
  prime[ 0 ] = 2; ind = 1;
  for(int i = 3; i < pr; i += 2)
    if(mark[ i ]) ind++; printf(\"%d\\n\", ind);
 }

回答11:

#include<stdio.h>
main()
{
    long long unsigned x,y,b,z,e,r,c;
    scanf(\"%llu\",&x);
    if(x<2)return 0;
    scanf(\"%llu\",&y);
    if(y<x)return 0;
    if(x==2)printf(\"|2\");
    if(x%2==0)x+=1;
    if(y%2==0)y-=1;
    for(b=x;b<=y;b+=2)
    {
        z=b;e=0;
        for(c=2;c*c<=z;c++)
        {
            if(z%c==0)e++;
            if(e>0)z=3;
        }
        if(e==0)
        {
            printf(\"|%llu\",z);
            r+=1;
        }
    }
    printf(\"|\\n%llu outputs...\\n\",r);
    scanf(\"%llu\",&r);
}    

回答12:

#include <iostream>

using namespace std;

int set [1000000];

int main (){

    for (int i=0; i<1000000; i++){
        set [i] = 0;
    }
    int set_size= 1000;
    set [set_size];
    set [0] = 2;
    set [1] = 3;
    int Ps = 0;
    int last = 2;

    cout << 2 << \" \" << 3 << \" \";

    for (int n=1; n<10000; n++){
        int t = 0;
        Ps = (n%2)+1+(3*n);
        for (int i=0; i==i; i++){
            if (set [i] == 0) break;
            if (Ps%set[i]==0){
                t=1;
                break;
            }
        }
        if (t==0){
            cout << Ps << \" \";
            set [last] = Ps;
            last++;
        }
    }
    //cout << last << endl;


    cout << endl;

    system (\"pause\");
    return 0;
}

回答13:

I know it\'s somewhat later, but this could be useful to people arriving here from searches. Anyway, here\'s some JavaScript that relies on the fact that only prime factors need to be tested, so the earlier primes generated by the code are re-used as test factors for later ones. Of course, all even and mod 5 values are filtered out first. The result will be in the array P, and this code can crunch 10 million primes in under 1.5 seconds on an i7 PC (or 100 million in about 20). Rewritten in C it should be very fast.

var P = [1, 2], j, k, l = 3

for (k = 3 ; k < 10000000 ; k += 2)
{
  loop: if (++l < 5)
  {
    for (j = 2 ; P[j] <= Math.sqrt(k) ; ++j)
      if (k % P[j] == 0) break loop

    P[P.length] = k
  }
  else l = 0
}

回答14:

#include<iostream>
using namespace std;

void main()
{
    int num,i,j,prime;
    cout<<\"Enter the upper limit :\";
    cin>>num;

    cout<<\"Prime numbers till \"<<num<<\" are :2, \";

    for(i=3;i<=num;i++)
    {
        prime=1;
        for(j=2;j<i;j++)
        {
            if(i%j==0)
            {
                prime=0;
                break;
            }
        }

        if(prime==1)
            cout<<i<<\", \";

    }
}