Find Prime Numbers In Java - Full Walkthrough with Source
ฝัง
- เผยแพร่เมื่อ 6 ก.ย. 2024
- Complete Java course: codingwithjohn...
Full source code available HERE: codingwithjohn...
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
amzn.to/36AfdUu
📕 One of my favorite programming books, Clean Code by Robert Martin
amzn.to/3GTPVhf
🎧 Or get the audio version of Clean Code for FREE here with an Audible free trial
www.audibletria...
🖥️Standing desk brand I use for recording (get a code for $30 off through this link!)
bit.ly/3QPNGko
📹Phone I use for recording:
amzn.to/3HepYJu
🎙️Microphone I use (classy, I know):
amzn.to/3AYGdbz
Donate with PayPal (Thank you so much!)
www.paypal.com...
☕Complete Java course:
codingwithjohn...
codingwithjohn...
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.
Of course that right, even for generate a n number of prime exists Sieve of Eratosthenes Math.srqt(numberToCheck), then for example por numberToCheck = 97 you need just 8 iteration for validate.
It's true i know of that optimisation,but is it really that much faster?Sqrt() call i think is slow,and even if its faster its still closet to same order of magnitude fast almost.We could say its O(n*sqrt(n))=O(n*n^1/2)=O(n^3/2)
@@ZeroSleap Yes, It is, I did a decade before in the university, while bigger num it going to be more efficiently.
Most of the time we use small number for test code < 1e4 think if we are test number like 2e7 or more.
Plus, you don't have to check even numbers, either. Just check the odd bumbers up to sqrt(num). We learnt at college.😉
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.
Dude, this is insane! I was playing around with a couple implementations of isPrime in python and while Jon's solution is up to 30% faster than what I initially came up with, your solution blows Jon's out of the water. On my machine, the equivalent of Jon's implementation takes 14 seconds to sieve the primes below 100,000. Your implementation takes about 3 seconds to sieve the primes below 1 mio!!! One thing i can't seem to get right is how to involve discarding factors based on the primes we already have in the list. Would appreciate it, if you could explain how to do that.
@@quitchiboo #You can try this code
import math
n = int(input("Enter n: "))
prime_numbers = [2]
print(2)
number_to_check = 3
while number_to_check math.sqrt(number_to_check)):
break
if isPrime:
prime_numbers.append(number_to_check)
print(number_to_check)
number_to_check += 2
@@quitchiboo Every number can be written as its prime factorization, meaning that a number is either prime such that it's a multiple of 1 and itself, or it is a multiple of 1 and some smaller prime numbers. Because we've already calculated every prime number less than the number to check, we can see if any of them are a factor. If none are, then the prime factorization must be 1 and itself, meaning it is prime. Again, we already know that 2 is not a prime factor because we're only checking odd numbers, and we know that we only need to check prime factors
John is showing a different way to solve the problem, you can definitely implement your solution any way that you want.
Great video I’ve seen this one and hangman very thorough and explained videos keep the great videos coming
Why not use "while(count
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
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.
Thank you John!
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
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.
10:56 instead of the if at line 32 having the condition,the while can hold that condition as well.
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.
Once again, your videos always seem to help me the most. Thanks John!
thank you, John! great video!
Finely tuned Rolex! With fresh batteries! 😆
Please Make videos on asymptotic notation s and how to find recursive algorithm time complexity
thank YOU!!!
Great tutorial
thanks!!! ur videos are great (:
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
thank you john!!!!!!!!!!!!!!!!!!
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
Good
why the numberToCheck is divied by 2? plz anyone there to let me understand this?
5:05 I am not supposed to use break outside a switch.
It can't be used outside of a switch or a loop. But it can definitely be used inside a loop.
@@CodingWithJohn 👍
Please Make videos on asymptotic notation s and how to find recursive algorithm time complexity...