Photo by Joshua Hoehne on Unsplash

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
Photo by Damon Lam on Unsplash

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:

Prime-counting function

We are going to use the second function to check the numbers.

Photo by Robin Schreiner on Unsplash

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.

SPrimes algorithm

Let’s compare it to other prime generator algorithms to see how it preforms.

Photo by Kelly Sikkema on Unsplash

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”.

--

--

Get the Medium app