# 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

**, 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.**

*N*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