May 29, 2021
A prime number generating algorithm
Prime number generator algorithms
⁰ A prime number can only be evenly divided by 1 & itself.
¹ The fundamental theorem of arithmetic states that any number can be factored into a unique list of primes. They are called composite numbers.
In this essay I try to tell you about prime number generation & an algorithm I managed to discover (hopefully).
It is based on a different idea that of already used prime algorithms.
Sections are as follows:
- Best way to determine if a number is prime
- The new algorithm
- Comparison with other prime number generator algorithms
Best way to determine if a number is prime
Let’s say we get a number N, and we have to determine if N is a prime or not.
Most intuitive function
Take all numbers in the range ]1;√N[ (not inclusive) and check If a number from this set, called i is the divisor of N, if it is, then N is not a prime. If it isn’t a divisor get the next number from the set and check it again. If we go trough the set without finding a divisor, then N is a prime.
As N approaches infinity then we can safely conclude that this algorithm will increase It’s runtime. Worst case time complexity is O(√N).
Faster function
If we know the prime numbers under N, then we just need to check for the prime numbers in the range ]1;√N/2+1[, (¹) which is half as much number as in the previous function.
Since all natural numbers are either prime, or composite (a factor of primes), this should work and be precise. The only drawback is that we already need to know some primes under √N/2+1 to start with.
Now comparing the two functions shows that the second function is 1.4 second faster on a set of [7;1 000 000[ numbers than the first “intuitive” one, it takes just 0.7091 seconds for the second algorithm to finish. Worst case with P primes is O(P) (where all n in P is smaller than √N/2+1) where:
We are going to use the second function to check the numbers.
The new algorithm
Let’s call the new algorithm SPrimes.
I might have found something while searching for a pattern in primes. I am still not sure If it’s really that unique but it’s still intresting.
If it’s really unique & this method wasn’t known before, then It can maybe help us understand primes better, or even it may have some applied use in different sciences or in life.
Let’s compare it to other prime generator algorithms to see how it preforms.
Comparison with other prime number generator algorithms
I measured the runtime of every algorithm here with this code structure:
import timeN = ...start_time = time.time()
result_1 = get_primes_sprimes(N) # Returns the N primes
end_time_1 = time.time() - start_time
Where N is the number of primes to be generated.
With version 1 of SPrimes I measured 1.330 seconds with N=10,000. Thats not really impressive, but I saw I can improve it. So version 2 on the same N finished in 0.035 seconds.
In the table below you can see SPrimes and other popular prime number generator algorithms compared on their runtime.
Conclusion
It seems like there is a lot to improve. But the fact that SPrimes is not a conventional way of finding primes (not a sieve), It’s still interesting to see how it preforms closely to other algorithms in runtime.
EDIT: This is not a new algorithm, the algorithm is found to be reducible for a simple “Check each odd number If it is a prime one”.
Author: Martin Kondor
