Find Prime Numbers In Java - Full Walkthrough with Source

Let's create program to find and print prime numbers from scratch in Java! We'll start by listing all prime numbers from 1 to 100, then modify it to find all prime numbers from 1 to n, then modify it to find the first n prime numbers.
Any way you need to find prime numbers in Java, we'll cover it!

This is a beginner friendly Java coding lesson tutorial, where we'll create a full Java program from scratch that finds prime numbers and prints them out to the console.

Learn or improve your Java by watching it being coded live!

Hey, I'm John! I'm a Lead Java Software Engineer who has been in the industry for more than a decade. I love sharing what I've learned over the years in a way that's understandable for all levels of Java developers.

Let me know what else you'd like to see!

Links to any stuff in this description are affiliate links, so if you buy a product through those links I may earn a small commission.

📕 THE best book to learn Java, Effective Java by Joshua Bloch

📕 One of my favorite programming books, Clean Code by Robert Martin

🎧 Or get the audio version of Clean Code for FREE here with an Audible free trial

🖥️Standing desk brand I use for recording (get a code for $30 off through this link!)

📹Phone I use for recording:

🎙️Microphone I use (classy, I know):

Donate with PayPal (Thank you so much!)

☕Complete Java course:

[mclgr]

To make the program faster, you could use the trick with the square root of number. You do not need to check the half of the numbers. Just check the numbers until the sqrt(num). We learnt that at collage.

[NamTran-hyuh]

Thank you, John. But I expected more things in this video.

To make the program much faster, we can initialize the primeNumbers list with [2], then start numberToCheck at 3 and add 2 to numberToCheck each loop. Because 2 is the only even prime number, so don't waste time checking even numbers.

Also, the factors used to check should be odd numbers as well and start with 3. For example, we wanna check If 101 is a prime number, we use odd numbers as factors, we need 25 loops (3, 5, 7, …, 101/2 = 49). This is better than 49 loops (2 to 50).

But this is still slower than we use the factor from the primeNumbers list that we already have. If we wanna check 101 is a prime number, we just need 14 loops (3 to 47). Because when we cannot divide 101 by 3, that means we cannot divide it by 9 and 27.

Finally, rather than check until numberToCheck/2, we can check until sqrt(numberToCheck), this belongs to mathematical analysis. With this method, we reduce 14 loops to 4 loops (3 5 7 11) to check if 101 is a prime number.

[raulalvarado]

Great video I’ve seen this one and hangman very thorough and explained videos keep the great videos coming

[mysterion]

Why not use "while(count <= limit)" instead of "while(true)" with a break? Also, you can skip all even numbers to make the algorithm faster.

[TUZZ]

For the variable "factor" we can take ready-made values ​​from the list of prime numbers. Not required to check all number again and again

[quiznos]

It would be cool to see a tutorial for finding primes using the Sieve of Eratosthenes, which is way more efficient at finding primes up to n compared to trial division while still being easy to implement.

[muhammetalimutlu]

that numberToCheck/2 confused me alot then i see already numbers that are biger than that cant divide the numberToCheck so you just preeliminate that part .Thank You its a really beneficial video

[AmiraMohamed-jftl]

The video explains it very well. Your naming of the variables and explanation of what exactly each step do helped a lot. It was hard to keep up with the articles and videos I watched before yours since they were using X and i without explaining what they really do. I also liked that you did it with user input and with count which provides more practice.

[epicsam]

It suffices to check divisibility by any number less than or equal to the square root of numberToCheck, since dividing by an integer greater than the square root leaves a factor less than the square root. Furthermore, one only needs to check divisibility by prime numbers, since divisibility by a composite number implies divisibility by its prime factors.

[AdrianTregoning]

Once again, your videos always seem to help me the most. Thanks John!

[ZeroSleap]

10:56 instead of the if at line 32 having the condition, the while can hold that condition as well.

[inandouttv]

Finely tuned Rolex! With fresh batteries! 😆

[anubhavtrivedi]

Please Make videos on asymptotic notation s and how to find recursive algorithm time complexity

[Garrison]

Thank you as always! you are a great wealth of information, I was also thinking if you were to add a example of starting from a input number to another input number like a lower limit and an upper limit. I messed around and got this..
rangeL = input.nextInt();
rangeH = input.nextInt();

int index = 0;
int amount = rangeH - rangeL;
int rangeArray = [amount];


for (int numToChk = rangeL; numToChk <= rangeH; numToChk++) {
boolean primevalue = true;
for (int factor = 2; factor <= numToChk/2; factor++) {
if (numToChk % factor == 0) {
primevalue = false;
break;
}
}
if (primevalue) {
rangeArray[index] = numToChk;
index++;
}
}

for (int i = 0; i < amount; i++) {
if (rangeArray[i] == null) {} else {
System, out, println(rangeArray[i] + " is a prime number");
}
}

[uttammehta]

Hi John as from last one month i am watching all your video it helped me lot right now I am doing the prime number problem but my time complexity is o(n) square can you say how can I right the program in such a way that is will take time complexity of √n

[asiis]

why the numberToCheck is divied by 2? plz anyone there to let me understand this?

[atrmenta]

5:05 I am not supposed to use break outside a switch.

[anubhavtrivedi]

Please Make videos on asymptotic notation s and how to find recursive algorithm time complexity...