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.

https://gist.github.com/markojerkic/90e64dad46de71529eb67c458b5284f8

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.

https://gist.github.com/markojerkic/8fd235039e447fc19e6d474169c27fcf

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.

https://gist.github.com/markojerkic/1fbf21159b2742f09c796902056e6be2

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