Skip to content
/ primery Public

Prime generator, used to compare different algorithms for generating prime numbers.

License

Notifications You must be signed in to change notification settings

cavoq/primery

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

46 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Primery

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.

license version

Supported algorithms

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))

Time comparisons

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.

Makefile

#### 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

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])

About

Prime generator, used to compare different algorithms for generating prime numbers.

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages