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!
20 Answers
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.
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.
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.
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.
This is an implementation of the Sieve of Eratosthenes in Python I've been toying with.
def eratosthenes(maximum: int) -> list[int | None]:
"""
Find all the prime numbers between 2 and `maximum`.
Args:
maximum: The maximum number to check.
Returns:
A list of primes between 2 and `maximum`.
"""
if maximum < 2:
return []
# Discard even numbers by default.
sequence = dict.fromkeys(range(3, maximum+1, 2), True)
for num, is_prime in sequence.items():
# Already filtered, let's skip it.
if not is_prime:
continue
# Avoid marking the same number twice.
for num2 in range(num ** 2, maximum+1, num):
# Here, `num2` might contain an even number - skip it.
if num2 in sequence:
sequence[num2] = False
# Re-add 2 as prime and filter out the composite numbers.
return [2] + [num for num, is_prime in sequence.items() if is_prime]
The code appears to take roughly 16s for 10000000 numbers on a humble Samsung Galaxy A40.
Suggestions are welcome!
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 (274,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.
I recently wrote this code to find the sum of numbers. It can be easily modified to find if a number is prime or not instead. Benchmarks are on top of the code.
// built on core-i2 e8400
// Benchmark from PowerShell
// Measure-Command { ExeName.exe }
// Days : 0
// Hours : 0
// Minutes : 0
// Seconds : 23
// Milliseconds : 516
// Ticks : 235162598
// TotalDays : 0.00027217893287037
// TotalHours : 0.00653229438888889
// TotalMinutes : 0.391937663333333
// TotalSeconds : 23.5162598
// TotalMilliseconds : 23516.2598
// built with latest MSVC
// cl /EHsc /std:c++latest main.cpp /O2 /fp:fast /Qpar
#include <cmath>
#include <iostream>
#include <vector>
inline auto prime = [](std::uint64_t I, std::vector<std::uint64_t> &cache) -> std::uint64_t {
std::uint64_t root{static_cast<std::uint64_t>(std::sqrtl(I))};
for (std::size_t i{}; cache[i] <= root; ++i)
if (I % cache[i] == 0)
return 0;
cache.push_back(I);
return I;
};
inline auto prime_sum = [](std::uint64_t S) -> std::uint64_t {
std::uint64_t R{5};
std::vector<std::uint64_t> cache;
cache.reserve(S / 16);
cache.push_back(3);
for (std::uint64_t I{5}; I <= S; I += 8)
{
std::uint64_t U{I % 3};
if (U != 0)
R += prime(I, cache);
if (U != 1)
R += prime(I + 2, cache);
if (U != 2)
R += prime(I + 4, cache);
R += prime(I + 6, cache);
}
return R;
};
int main()
{
std::cout << prime_sum(63210123);
}
I found this solution pretty fast but it comes with consequences, So this is called Fermat's Little Theorem. If we take any number p and put that in (1^p)-1 or (2^p)-2...(n^p)-n likewise and the number we get is divisible by p then it's a prime number. Talking about consequences, it's not 100% right solution. There are some numbers like 341(not prime) it will pass the test with (2^341)-2 but fails on (3^341)-3, so it's called a composite number. We can have two or more checks to make sure they pass all of them. There is one more kind of number which are not prime but also pass all the test case:( 561, 1729 Ramanujan taxi no etc.
The good thing: With
(2^p)-2in first 25 billion numbers only 2183 fails this case.
#include <iostream>
#include <math.h>
using namespace std;
int isPrime(int p)
{
int tc = pow(2, p) - 2;
if (tc % p == 0)
{
cout << p << "is Prime ";
}
else
{
cout << p << "is Not Prime";
}
return 0;
}
int main()
{
int p;
cin >> p;
isPrime(p);
return 0;
}
Another Python implementation that is more straightforward and slightly faster* than the one in the answer of Death Mask Salesman:
import numpy as np
def prime_numbers(limit: int) -> list[int]:
"""Provide a list of all prime numbers <= the limit."""
is_prime = np.full((limit + 1, ), True)
is_prime[0:2] = False
for n in range(2, limit + 1):
if is_prime[n]:
is_prime[n**2::n] = False
return list(np.where(is_prime)[0])
You could further optimize by, e.g., excluding the 2, or by hard-coding even more prime numbers, but I wanted to keep it simple.
*exemplary runtime comparison (note: I used the optimized form of the other implementation, see my comment):
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.
i wrote it today in C,compiled with tcc, figured out during preparation of compititive exams several years back. don't know if anyone already have wrote it alredy. it really fast(but you should decide whether it is fast or not). took one or two minuts to findout about 1,00,004 prime numbers between 10 and 1,00,00,000 on i7 processor with average 32% CPU use. as you know, only those can be prime which have last digit either 1,3,7 or 9 and to check if that number is prime or not, you have to divide that number by previously found prime numbers only. so first take group of four number = {1,3,7,9}, test it by dividing by known prime numbers, if reminder is non zero then number is prime, add it to prime number array. then add 10 to group so it becomes {11,13,17,19} and repeat the process.
#include <stdio.h>
int main() {
int nums[4]={1,3,7,9};
int primes[100000];
primes[0]=2;
primes[1]=3;
primes[2]=5;
primes[3]=7;
int found = 4;
int got = 1;
int m=0;
int upto = 1000000;
for(int i=0;i<upto;i++){
//printf("iteration number: %d\n",i);
for(int j=0;j<4;j++){
m = nums[j]+10;
//printf("m = %d\n",m);
nums[j] = m;
got = 1;
for(int k=0;k<found;k++){
//printf("testing with %d\n",primes[k]);
if(m%primes[k]==0){
got = 0;
//printf("%d failed for %d\n",m,primes[k]);
break;
}
}
if(got==1){
//printf("got new prime: %d\n",m);
primes[found]= m;
found++;
}
}
}
printf("found total %d prime numbers between 1 and %d",found,upto*10);
return 0;
}
This is the fastest algorithm to find all prime numbers from 1 to n(on my pc it found all from 1 to 1000000 just for 0.004 seconds).
#include <iostream>
#include <fstream>
using namespace std;
double FindPrime(bool* array, int size){
clock_t start;
double runtime;
for (int i = 2; i < size; i++)
array[i] = true;
start = clock();
for (int i = 2; i <= size; i++)
if (array[i])
for (int j = 2 * i; j < size; j += i)
array[j] = false;
runtime = (double)(clock() - start) / CLOCKS_PER_SEC;
return runtime;
}
int main() {
ofstream fout("prime.txt");
int n = 0;
cout << "Enter the upper limit of prime numbers searching algorithm:";
cin >> n;
bool* array = new bool[n + 1];
double duration = FindPrime(array, n + 1);
printf("\n%f seconds.\n", duration);
for (int i = 2; i <= n; i++)
if (array[i])
fout << i << endl;
fout.close();
return 0;
}
solution to find factors:
def divisors(integer):
result = set()
i = 2
j = integer/2
while(i <= j):
if integer % i == 0:
result.add(i)
#it dont need to
result.add(integer//i)
i += 1
j = integer//i
if len(result) > 0:
return f"not prime {sorted(result)}"
else:
return f"{integer} is prime"
--- Tests ---- import time
start_time = time.time()
print(divisors(180180180180))
print("--- %s seconds ---" % (time.time() - start_time))
--- 0.06314539909362793 seconds ---
start_time = time.time()
print(divs(180180180180180))
print("--- %s seconds ---" % (time.time() - start_time))
--- 1.5997519493103027 seconds ---
start_time = time.time()
print(divisors(1827))
print("--- %s seconds ---" % (time.time() - start_time))
--- 0.0 seconds ---
start_time = time.time()
print(divisors(104729))
print("--- %s seconds ---" % (time.time() - start_time))
--- 0.0 seconds ---
with this code:
def divs(integer):
result = set()
i = 2
j = integer / 2
loops = 0
while (i <= j):
if integer % i == 0:
print(f"loops:{loops}")
return f"{integer} is not a prime"
i += 1
j = integer // i
loops += 1
print(f"loops:{loops}")
return f"{integer} is prime"
--- Tests ---
start_time = time.time()
print(divs(180180180180180180180180))
print("--- %s seconds ---" % (time.time() - start_time))
--- 0.0 seconds ---
#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<<", ";
}
}
Related