Home About Login Current Archives Announcements Editorial Board
Submit Now For Authors Call for Submissions Statistics Contact
Home > Archives > Volume 20, No 7 (2022) > Article

DOI: 10.14704/nq.2022.20.7.NQ33080

Evaluation For Algorithms for Finding the Prime Numbers

Iyas Ahmad Abdul Rahman Qaddara, Prof. Saleh Irshied Oqeili


Prime numbers are unique and distinctive numbers. It only has one division factor, which is made up of the numbers 1 and the number itself. Finding prime numbers from 1 to N can be done manually, but an algorithm for finding primes is required to find primes on a large range (large N). The main goal of this study is to conduct a comparison study between the algorithms used to find prime numbers, which are the Sieve of Eratosthenes, Segmented Sieve, Sieve of Sundaram, Bitwise Sieve, and Sieve of Atkin, and determine which algorithm is better used for small or large primes by terms of time complexity and the range of number, Where this study will explain in detail the impact of each algorithm on the computer resources and which one is better than this one, and on the other hand, it will clarify the time for each algorithm, specifying the best algorithm, determining the maximum inputs of these algorithms and when they give their high efficiency, comparing all cases and determining the best. The numbers will splitted into two parts: small up to 1000,000,000 and large up to 1000,000,000,000,000, and applied on the five algorithms. This study shows that sieve of Sundaram algorithm up to 1000, 00 its better algorithm comparing for the rest, but after the increase of range numbers and increase the computation of the algorithm, its efficiency decrees and Sieve of Eratosthenes give result better up to 1000,000,000. And the whole algorithm gives 100% accuracy of generated prime numbers on small range. While large numbers , Segmented Sieve more efficient up to 1000,000,000,000 From the rest of algorithms but it’s still close to sieve of Atkin, then the segmented sieve efficient decreasing and the sieve of Atkin clearly will be more efficient at 1000,000,000,000,0 and more, Sieve of Eratosthenes didn’t allow numbers more than 9-digits because the size of array it’s become large and didn’t fit the memory , while sieve of Sundaram take up to 10 digits just but need time more than segmented sieve and atkins , bitwise sieve take up 1012 numbers with more time comparing with the other algorithm by take the huge different of space, but the the accuracy of bitwise sieve on large numbers not 100%, its roundly 98.8%, its discards some prime number from the list without aware it then compare by the bits


Prime numbers are unique and distinctive numbers

Full Text