The Comparison of Methods for Generating Prime Numbers between The Sieve of Eratosthenes, Atkins, and Sundaram

Main Article Content

Muhammad Khoiruddin Harahap Nurul Khairina

Abstract

Prime numbers are unique numbers. Prime numbers are numbers that only have a dividing factor consisting of numbers 1 and the number itself. The prime numbers from 1 to n that are relatively small can be generated manually, but a prime number generator algorithm is needed to generate prime numbers on a large scale. This study compares three prime number generator algorithms, namely: The Sieve of Eratosthenes, The Sieve of Atkins, and The Sieve of Sundaram. These three sieve algorithms have their own differences in generating prime numbers. The Sieve of Eratosthenes uses a simpler method by crossing multiples of prime numbers and marking them as non-prime numbers. The Sieve of Atkins uses several requirements for quadratic equations and modulus in determining prime numbers. The Sieve of Sundaram has an algorithm similar to The Sieve of Atkins, but there are requirements for linear equations to determine prime numbers. This study aims to see a comparison of these three algorithms in terms of accuracy and speed in generating prime numbers on a large scale. The results of this study indicate The Sieve of Eratosthenes, Atkins and Sundaram algorithms can generate large numbers of prime numbers with good accuracy, this was tested by the Fermat Primality Test Algorithm. The conclusion that can be drawn from this study, The Sieve of Eratosthenes have a faster time to generate prime numbers on a large scale than the other two algorithms.

Downloads

Download data is not yet available.

Article Details

How to Cite
HARAHAP, Muhammad Khoiruddin; KHAIRINA, Nurul. The Comparison of Methods for Generating Prime Numbers between The Sieve of Eratosthenes, Atkins, and Sundaram. SinkrOn, [S.l.], v. 3, n. 2, p. 293-298, apr. 2019. ISSN 2541-2019. Available at: <http://jurnal.polgan.ac.id/index.php/sinkron/article/view/10129>. Date accessed: 24 oct. 2019. doi: https://doi.org/10.33395/sinkron.v3i2.10129.
Section
Articles
**************** Abstract viewed = 182 times ****************

References

A Comparative Analysis of General, Sieve-of-Eratosthenes and Rabin-Miller Approach for Prime Number Generation 2019 International Conference on Electrical, Computer and Communication Engineering (ECCE) 1-4 Bangladesh IEEE

Contrast Various Test For Primality 2016 International Conference on Accessibility to Digital World (ICADW) 1-6 Guwahati IEEE

Experimenting Large Prime Numbers Generation in MPI Cluster 2016 International Congress on Information and Communication Technology, Advances in Intelligent Systems and Computing 61-66 Gujarat Springer Singapore

Generating Mersenne Prime Number Using Rabin Miller Primality Probability Test to Get Big Prime Number Cryptography in RSA 2017 International Journal of Information System & Technology 1-7

Modular Class Primes in the Sundaram Sieve 2018 International Journal of Mathematical Education in Science and Technology 1-4

Primality Tests Based on Fermat’s Little Theorem 2006 Guwahati Springer, Berlin, Heidelberg

Prime Generating Algorithms by Skipping Composite Divisors 2014 International Journal of Computer Science & Engineering Technology (IJCSET) 935-940

Prime Sieve Using Binary Quadratic Forms 2003 Mathematics of Computation 1023-1030

Refinement of Prime Generating Algorithms 2015 International Journal of Innovative Science, Engineering & Technology (IJISET )21-24

Study on Deterministic and Probabilistic Computation of Primality Test 2019 International Conference on Sustainable Computing in Science, Technology & Management (SUSCOM) 2206-2212 Jaipur: India Elsevier SSRN

The Genuine Sieve of Eratosthenes 2009 Journal of Functional Programming (JEP) 95-106

Two compact incremental prime sieves 2015 LMS J. Comput. Math.675–683

https://www.w3resource.com/python-exercises/math/python-math-exercise-21.php (Accessed on : Mei 20, 2019)

http://pythonfiddle.com/atkin-sieve/ (Accessed on : Mei 16, 2019)

https://www.geeksforgeeks.org/sieve-sundaram-print-primes-smaller-n/ (Accessed on : Mei 18, 2019)