Which is the fastest algorithm to find prime numbe

Question

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!

Answer 1

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.

Answer 2

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