Primery is used to generate prime numbers in a specified range [x, y]. It also measures the time each algorithm needs to generate the prime numbers. It`s planned to expand the usage for checking primes as well and perfoming other operations.
| Algorithm | Complexity |
|---|---|
| Trial Division | O(n*sqrt(n)) |
| Sieve of Eratosthenes | O(n*log(log(n))) |
| Sieve of Sundaram | O(n*log(n)) |
| Sieve of Atkin | O(n)) |
Hardware:
CPU: 11th Gen Intel© Core™ i7-11800H @ 2.30GHz × 8
GPU: Intel Corporation TigerLake-H GT1 [UHD Graphics]
Single threaded:
| n | Sieve of Eratosthenes | Sieve of Sundaram | Sieve of Atkin |
|---|---|---|---|
| 10⁵ | 0.718 ms | 0.602 ms | 0.936 ms |
| 10⁶ | 7.544 ms | 6.956 ms | 8.386 ms |
| 10⁷ | 66.149 ms | 65.015 ms | 62.988 ms |
| 10⁸ | 0.947 s | 1.007 s | 0.837 s |
| 10⁹ | 10.956 s | 16.559 s | 8.839 s |
Mulit threaded:
| n | Sieve of Eratosthenes | Sieve of Sundaram | Sieve of Atkin |
|---|---|---|---|
| 10⁵ | 3.197 ms | 27.105 ms | 10.941 ms |
| 10⁶ | 11.735 ms | 140.159 ms | 40.063 ms |
| 10⁷ | 62.772 ms | 1.195 s | 122.007 ms |
| 10⁸ | 0.49 s | 11.984 s | 0.511 s |
| 10⁹ | 7.284 s | - | 3.903 s |
Conclusion:
Based on the data in the tables, it appears that the Sieve of Atkin is the fastest algorithm for generating prime numbers in both single-threaded and multi-threaded environments. In single-threaded mode, it is faster than the other two algorithms for all values of n tested. In multi-threaded mode, it is still the fastest algorithm for n up to 10⁸, and is competitive with the Sieve of Eratosthenes for n = 10⁹. The Sieve of Sundaram is slower than the other two algorithms in both single-threaded and multi-threaded mode. For large inputs, multithreading gives a great perfomance boost for generating prime numbers.
#### primery v1.2 ####
Available targets:
build Build software
clean Remove program and output files
help Get help for Makefile
install Install software globally
uninstall Uninstall software
USAGE: primery [Options] {algorithm}
EXAMPLE: primery -i [234,100000] -t ms -m p sieveOfEratosthenes
SUPPORTED ALGORITHMS:
{ td | trialDivision }
{ soe | sieveOfEratosthenes }
{ sos | sieveOfSundaram }
{ soa | sieveOfAtkin }
OPTIONS:
-h, --help: Get help for the program
-o, --output: Specify an output file for the generated prime numbers (default is primes.txt)
-m, --mode: Specify a mode for generating prime numbers [s | single, p | parallel] (default is single)
-t, --time: Specify time format [ns | nanoseconds, ms | milliseconds, s | seconds] (default is milliseconds)
-i, --interval: Specify interval to generate prime numbers in format [start,end] (default is [2,1000])
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent