Java: Let's Practice - Prime Numbers

Let's write a program to find all the prime numbers between two numbers - 

I have already explained in my earlier post - Why Logic Blocks?, that logic thinking is very important for problem solving and writing programs. So, we will build the logic to examine how we can find all the prime numbers between two numbers.

What are the prime numbers?

Prime numbers are which can be wholly divided by 1 or itself, but not any other number. Or in other words, you can say that the number is a prime number if it has only two factors - 1 and itself.

Create a logic

Suppose, we have two numbers 2 and 50, and we have to find prime numbers between these two numbers. 

1. We need to check each and every number to find all the prime numbers, but logic will be the same for each number. So, we need a for loop to repeat the logic for each number between 2 and 50. This loop will be iterate between numbers 2 and 50. For Loop and For-each Loop
2. But we know, that all even numbers can be divided by 2, and they can't be the prime numbers. We will avoid checking even numbers. So, for loop will run for only odd numbers starting from 3 to 49.
3. If they are not even numbers, we should not check the odd numbers dividing by even numbers. We will avoid by dividing only by odd numbers. So, there will be another inner for loop which will run between 3 and till the number we are checking for in outer (step 2) for loop.
4. We need a Boolean variable to set, if the number is prime - set it true, and if number is not prime - set it false. We will use remainder operator (%) (Arithmetic Operators) to determine if the number can be divisible by another number. Initially set prime boolean value as true, if remainder is 0 then set prime boolean value as false. And once it is proved that the number is not prime number, you come out from the inner loop, no need to continue for more checking. We use break statement to come out from the loop. Break Statement
5. Print only the numbers which have prime boolean value as true, when come out from the inner loop.

Program to find the prime numbers between 2 and 50

Class PrimeNumber (PrimeNumber.java)

public class PrimeNumber {
    public static void main(String args[]) {
        // Find prime numbers between n1 and n2
        int n1 = 2, n2 = 50;

        // Set as the number is prime
        boolean prime = true;
        // Check only odd numbers
        for(int i = 3; i < n2; i = i + 2) { // Outer Loop
            // Divide by only odd numbers and till outer loop number
            for(int j = 3; j < i; j = j + 2) { // Inner Loop
                // If remainder is 0 then number is not prime
                if((i % j) == 0) {
                    prime = false;
                    break;
                }
            }
            if(prime) System.out.print(i + " ");
            prime = true;
        }
        System.out.println(" ");
    }
}

Let's analyze above program using the logic steps above -

for(int i = 3; i < n2; i = i + 2) {}

Outer for loop in above statement, starts with initializing a local variable i with value 3 and runs the loop till i's value as n2 (50). And in the increment part, the value of i is incremented by 2 to avoid even numbers. The loop will run for possible values of i => 3, 5, 7, 9, 11, .......... , 49

for(int j = 3; j < i; j = j + 2) {}

Inner for loop in above statement, starts with initializing a local variable j with value 3 and runs the loop till j's value as i's value in outer loop. And also in the increment part, the value of j is incremented by 2 to avoid division by even numbers. The loop will run for possible values of j -

• if i = 3 then no inner loop. 
• if i = 5 then j => 3
• if i = 7 then j => 3, 5
• if i = 13 then j => 3, 5, 7, 9, 11

if((i % j) == 0) {
    prime = false;
    break;
}

As soon as program finds that number is not the prime number, it comes out from the inner loop and continues the outer loop.

if(prime) System.out.print(i + " ");

If the number is prime, it will continue the inner loop till all the possible values of j and then print the number. Output will be like -

3 5 7 11 13 17 19 23 29 31 37 41 43 47

Note: Here in the above program, I tried to simplify the logic and convert into the program instructions. In reality, the problems are very complex. You just have break them down to simple steps and then create the logic. I hope this post is helpful for the brginners who are learning how to program.