If you are not aware of What are prime numbers and How to generate prime numbers up to 100 or any given range, In this article, you will learn to develop a Java program to find Prime numbers – Step by Step.
So, let’s get started point by point-
Learning Points-
- What are the Prime Numbers?
- Solution 1 – Logic behind code
- Explained – How algorithm verifies it?
- Solution 2 – When range is given
- Output of the program
Conclusion
What are the Prime Numbers
In simple words, Prime numbers are special natural numbers that are greater than 1 and are only divided by 1 and themselves.
For example, 7 is a prime number because it can only be divided by only 1 and 7.
However, 8 is not a prime number because it can be divided by 1, 2, and 8 itself.
Now, we know what are the prime numbers, now let’s understand, how to find prime numbers.
#1. Logic (Behind the Solution)
If you have observed carefully then you might already know that, if a number K is not divisible by any other number which is less than OR equal to square root of that number K, then the number K is a prime number.
Let’s develop a Java program to understand it better:
package com.shubhamklogic.java.tutorials;
public class FindPrimeNumberSolutions {
public static void main(String[] args) {
System.out.println("19 is prime number?: " + isPrimeNumber(19) );
System.out.println("100 is prime number?: " + isPrimeNumber(100) );
System.out.println("31 is prime number?: " + isPrimeNumber(31) );
System.out.println("23 is prime number?: " + isPrimeNumber(23) );
System.out.println("49 is prime number?: " + isPrimeNumber(49) );
}
public static boolean isPrimeNumber(int number)
{
for (int k = 2; k <=Math.sqrt(number); k++) { // STEP 1: CHECKING SQUARE ROOT
if( number%k == 0 ) // STEP 2: CHECKING IF REMAINDER IS ZERO?
return false;
}
return true;
}
}
Output:
It’s a simple Java program to find Prime numbers. As, you’ll run the above Java program, you’ll see the below output-
19 is prime number? : true 100 is prime number? : false 31 is prime number? : true 23 is prime number? : true 49 is prime number? : false
Complete Explanation
How did the above Java Program verify the Prime Numbers : Step-by-Step
In the above Java example, we had a number 100, and we passed that number to our isPrimeNumber() method. Here is how our algorithm calculate – whether 100 is a prime number or not-
1) The square root of 100 is 10. Let’s say, a and b are numbers and a x b = 100, for various pairs of a and b.
If a == b, then they are equal numbers, and are the square root of 100, simple. Which is 10.
2) In a and b, If one of them is less than 10 (which is a square root of 100), the other number has to be greater than 10. For example, 5 x 20 == 100. Here, 20 is greater than 10, and the other number 5 is lesser than 10.
3) Thinking about a x b, if one of them goes down, the other must get bigger to compensate, so the multiplication stays at 100. Here, observe one thing- They pivot around the square root (which is 10 in this case).
4) The square root of 101 is about 10.049875621. So if you’re testing- whether the number 101 is prime or not, then you only need to try the integers up through 10 (including 10).
Remember*** If there’s a pair of factors with one of the numbers bigger than 10, the other number of the pair has to be lesser than 10 (The square root). If the smaller one doesn’t exist, there is no matching larger factor of 101.
5) If you’re testing 121, the square root is 11. You just need to test the prime integers from 1 to 11 (inclusive) to see if it goes in evenly. 11 goes in 11 times, so 121 is not prime. If you had stopped at 10, and not tested 11, you would have missed 11.
As a conclusion, You have to test every prime integer greater than 2, but less than or equal to the square root.
#2. How many Prime numbers between 1 and 100
Sometimes you need to find Prime numbers in any given range such as between 1 to 100 or 20 to 30 etc. For that, here is an easy Java program-
package com.shubhamklogic.java.tutorials;
public class FindPrimeNumberSolutions {
public static void main(String[] args) {
int startingRange, endingRange, i, flag;
// Take input
startingRange = 1; endingRange=100;
System.out.println("Prime numbers between "+ startingRange
+ " and "+ endingRange +" are: ");
primeNumbersInRange( startingRange , endingRange );
}
public static void primeNumbersInRange( int startingRange, int endingRange) {
int i, flag;
// Now Iterate until startingRange is not equal to endingRange
while (startingRange < endingRange) {
flag = 0;
// Just ignore the integers less than 2
if (startingRange <= 1) {
++startingRange;
continue;
}
// if the startingRange is a non-prime number, flag will be 1
for (i = 2; i <= startingRange / 2; ++i) {
if (startingRange % i == 0) {
flag = 1;
break;
}
}
if (flag == 0)
System.out.print(startingRange+" ");
// To check prime for the next number
// You need to increase startingRange by 1
++startingRange;
}
}
}
Output:
When you’ll run the above Java program to find prime numbers between 1 to 100, you will successfully get a list of prime number –
Prime numbers between 1 and 100 are: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
Wrap Up
So far, In this Java tutorial, we learned 2 Easy ways to develop a Java program to find Prime numbers. We have also understood the logic behind the code.
I hope you found this tutorial helpful. Check out other related Java articles that you may like: