Finding prime numbers is one of the classic algorithm problems. It was the first problem I tried to solve on my own. I bought Java: A Beginner’s Guide by Herbert Schildt, and up until then, I never tried to solve anything myself. It took be about two days to come up with a working solution. It didn’t actually work. I didn’t know about modulos, so I made a very janky algorithm that worked for integers in the range from 2 to 49.
The solution that the book provided was the classic nested for loop method. Although it is a very slow method, with the time complexity of O(), it is the most basic method, so we’re going to go through it.
Nested loop method
As I said, this is a very basic solution. It is effective, but it can be improved.
I made a slight modification to the code. It’s a very small change, but it does improve the algorithm’s efficiency.
As you can see, for every integer i, we loop through numbers in the range from 2 to i-1. Although not mathematically, this algorithm perform with the time complexity of O().
Going through the known prime numbers
What if we didn’t have to go through each number from 2 to the same number for each of the numbers in our given range. Technically, we only need to check the modulo of number with the preceding prime numbers. Each time we discover new prime number, we add it to the list, so the next number will have one more condition.
The time complexity of this algorithm is O(nm), where n is the given upper bound – 2 and m is the size of the result list.
Sieve of Eratosthenes
Sieve of Eratosthenes is an ancient method of finding prime numbers. It start from the first known prime number – 2. From there it removes every 2nd value (excluding the number 2) from the list of possible prime numbers. From there, it moves to the next available integer, and now that integer is 3. We remove every third integer from the 3 (excluding the number 3). The next available number is 5 and so on it goes until we reach our upper bound.
This bit of code is inspired by the source code from the Princeton University website.
This algorithm run in the time complexity of O(n log n).
Other possible algorithms
There are many algorithms for finding prime numbers. Most of the time, you can get away by using the second method. But for those of you that want to look through few more ways of tackling this problem, you can check out these algorithms:
- Sieve of Atkin
- Miller–Rabin primality test