In this post, we will discuss how to write a simple Java program to find prime numbers between 1 and 100. We will be using a simple algorithm implemented in nested loops. So let us get started!
What is a prime number?
A prime number is a number which can only be divided by 1 and itself. In other words, you will not be able to find any other number that you can divide the prime number by without having fractional result part or a remainder. Examples of prime numbers are 2, 3, 5, 7 and lucky number 13.
Testing if a number is prime (the primality test)
There are many algorithms designed over the years that can test if a number is prime or not. In our example, we will use the most simple method, which is called trial division.
In trial division, the number to test is being “divided” by all numbers from 2 to n / 2. If the results of the divisions never yields a zero remainder, then the number is a prime number. Let us try with a then number 13:
- divide 13 by 2. Result is 6 and remainder is 1. Keep going..
- divide 13 by 3. Result is 4 and remainder is 1. Keep going..
- divide 13 by 4. Result is 3 and remainder is 1. Keep going..
- divide 13 by 5. Result is 2 and remainder is 2. Keep going..
- divide 13 by 6. Result is 2 and remainder is 1. Keep going..
- Next divisor is 7 which is more than 13/2. Stop. Since all divisions yielded a remainder, the number 13 is prime.
Notice that we only care about the remainder and not the actual result. Therefore, in the next section, we will be using the modulus operator to find out the remainder. If you are unfamiliar with the modulo operator, you can learn more about it here
Implementation in Java
Let us start with the implementation in Java. We will use the algorithm mentioned in the previous section. For this, we will need to define a loop from 1 to 100 in order to find all prime numbers from 1 to 100. We will use a for loop for this:
//We want to test from 1 to 100
for(int i = 1; i< 100; i++){Our next step is to test the number i with the modulus operation of every number from 2 till i/2 as previously discussed. For this we need a second nested loop. If we find a divisor, we will need to remember that we did. Therefore, we will also define a boolean flag that we will set to true, if we found a divisor.
boolean divisorFound = false;
//now we test the number i if it is prime
for (int j = 2; j <= i/2; j++){Notice that we created the new counter j for our nested loop. This is because i is already defined within our scope. So we will need a new variable. Notice also that we stop at j <= i/2 and not j < i/2 . This is because the result of 4 / 2 is a 2, which is not more than 2. Therefore, for the number 4, we never enter the loop and our program thinks that there is no divisor for the number 4, which is not correct.
Our next step is to test the remainder of the division of i / j. For this, we test if the result of the modulo is a zero. If it is, then we found divisor and our number is not a prime number.
//check for division remainder
if(i%j==0){
divisorFound = true;
}
}If a the result of the modulo is a 0, then a divisor is found and we set the flag to true. Notice that if we find a divisor, we do not need to continue inside our nested loop as we already know that the number is not prime. Therefore, it would be more effecient to add a break statement. A break statement terminates our nested loop so we will not need to continue with the rest of the numbers from j to i/2. After adding the break statement, our if condition will look as follows:
//check for division remainder
if(i%j==0){
divisorFound = true;
break;
}Our final step is to simply print the number on the screen if it is a prime number. Therefore, our complete program will look as follows:
package com.nullbeans;
public class Main {
public static void main(String[] args) {
//We want to test from 1 to 100
for(int i = 1; i< 100; i++){
boolean divisorFound = false;
//now we test the number i if it is prime
for (int j = 2; j <= i/2; j++){
//check for division remainder
if(i%j==0){
divisorFound = true;
break;
}
}
//if no divisor is found, announce that this is a prime number
if(!divisorFound){
System.out.println("Found prime number : "+ i);
}
}
}
}
If we run our program, this will be our output:
Found prime number : 1 Found prime number : 2 Found prime number : 3 Found prime number : 5 Found prime number : 7 Found prime number : 11 Found prime number : 13 Found prime number : 17 Found prime number : 19 Found prime number : 23 Found prime number : 29 Found prime number : 31 Found prime number : 37 Found prime number : 41 Found prime number : 43 Found prime number : 47 Found prime number : 53 Found prime number : 59 Found prime number : 61 Found prime number : 67 Found prime number : 71 Found prime number : 73 Found prime number : 79 Found prime number : 83 Found prime number : 89 Found prime number : 97 Process finished with exit code 0
Why prime numbers are so important?
Finding large prime numbers is a task used often performed by technical, cryptographic and scientific applications. For example, prime numbers are used when performing asymmetric encryption. Asymmetric encryption is a type of encryption used to secure transactions, such as online credit card transactions or when logging into a secure platform. Some cryptographic algorithms generate a “password” which is the product of the multiplication of two prime numbers. Each end of the transaction takes one of the prime number, and the other takes the second number. You can then only decrypt the transaction by having one of the two prime numbers. In that case it would make sense to have a huge prime number, so that an attacker would have a hard time guessing it.
Finding the large prime number is a quest many seek to explore, not just for the challenge but even for financial rewards. For example, the Electronic Frontier Foundation offers up to $250K for whoever finds a prime number with more than a billion decimal digits!
If you attempt this yourself, then please note that you will need to use a data structure other than an integer in Java as it would be too small. We would need to use a “BigInteger” for example. We will explore BigIntegers in a later tutorial. You will also need a large amount of computing resources and storage for this 🙂
Summary
In this tutorial, we discussed briefly what a prime number is. We discussed the trial division algorithm for finding primes and how to implement this algorithm in Java. We then discussed the motivation behind finding prime numbers and why they are important in real life. If you liked our article then please make sure to subscribe to our twitter feed by clicking on the follow button below 🙂