Is coding a program for finding Primes as straight as it appears?
All of you, at some point of time, in your journey towards becoming a programmer may have surely been thrown this question — Write a program to check whether a given number is a prime.
The first thing that needs to be figured out is — What do you mean by a prime number?
Prime number is the one which is not completely divisible by any number except 1 and itself.
Numbers divisible by any other number other than 1 and itself are called Composite numbers.
Now to start writing a code for figuring out whether or not a number is Prime, you need to think of what approach to take — and the definition of prime numbers makes it pretty clear.
For a number to be prime it should not be divisible by any number other than 1 and the number itself. So naturally we start dividing the number by 2 and continue dividing it with consecutive numbers till we reach the numbers itself. If at any point we find it to be divisible by any number, its not a prime!!
So the overall approach seems to be sorted now. When do you say a number x is divisible by a number y? Flash back to your school days and you know x is divisible by y if the remainder of x divided by y is 0.
Here is an example checking whether 5 is a prime number
Here is another example checking whether 25 is a prime number
We have the ammunition ready. Let’s attack the problem.
One way to go about it
import java.util.Scanner;
public class Prime {
public static void main(String[] args) {
int num, i; /* This is used as an indicator flag indicating whether
or not the number is prime*/
boolean flag = true;
Scanner scan = new Scanner(System.in); /*Ask the user to enter a number to be checked for being
a prime */
System.out.print("Enter a Number : "); /*Store the number entered in a variable*/
num = scan.nextInt(); /* For a number to be prime it must not be divisible
by any number other than 1 and itself. So we need
to start dividing it by 2 and go on till one less
than the number*/
for(i=2; i<num; i++)
{
/* Check if entered number is divisible by current
iterating number */
if(num%i == 0)
{
/*If its divisible, its surely not a prime.
So set indicator flag false*/
flag=false;
/*Once you find it to be divisible by one
number, it is surely not prime no matter
how many more numbers it is or is not
divisible by..so no point checking further.
Break out of the loop...Save iterations!!*/
break;
}
}
/* Your main work is done. Now just check the status of
the indicator flag and accordingly display the
result*/
if(flag)
{
System.out.print("This is a Prime Number");
}
else{
System.out.print("This is not a Prime Number");
}
}
}
So why do you think we needed a flag here?
Well, a flag was needed because if the number turns out to be divisible by even a single number it is sufficient proof to conclude that the number is not a prime. But the same is not true for concluding that the number is prime. Can you conclude that the number is prime if its not divisible by just one number? No, it may be divisible by some other number you have not yet checked it with, right?? This conclusion can be made only and only after the entire loop is done executing — that is, when you are sure it is not divisible by ANY numbers in the range 2 to number-1. So if the number is divisible by any of the numbers in the range the flag is set to false, but if the number is not divisible by any of the numbers in the range the flag will maintain its true status and then you can rightly conclude its prime.
But variable means additional baggage for any language. Every time you declare a variable you are claiming certain amount of space in the finite memory present on your system. So saving every bit of unnecessary memory is crucial.
So do you think we can do away with the flag variable here? Think for a moment — what if the flag variable was not present?
In other words, if the for loop iterated fully without encountering the break statement, then we know that the number is prime. One of the simplest ways to know whether for loop completed is to check if its i equals num — we had instructed the loop to iterate till value of i is less than num , so for loop will complete iteration when i becomes equal to num.
If the number was composite and break was encountered then i would never be equal to num otherwise for loop would not have entered the current iteration itself, right?
So a slight modification to the above program will enable us to achieve the same thing with one variable less and hence in a more efficient way.
Here is the modified version
import java.util.Scanner;
public class Prime {
public static void main(String[] args) {
int num, i;
Scanner scan = new Scanner(System.in); /*Ask the user to enter a number to be checked for being
a prime */
System.out.print("Enter a Number : "); /*Store the number entered in a variable*/
num = scan.nextInt(); /* For a number to be prime it must not be divisible
by any number other than 1 and itself. So we need to
start dividing it by 2 and go on till one less
than the number (There are more efficient ways to
write this loop as well */
for(i=2; i<num; i++)
{ /* Check if entered number is divisible by
current iterating number */
if(num%i == 0){
break;
}
} /* Your main work is done now just check whether
for loop has iterated completely and
accordingly print the result */ if(i == num){
System.out.print("This is a Prime Number");
}
else{
System.out.print("This is not a Prime
Number"); } }}
These were the two ways in which the prime number problem could be solved. Though it seems a pretty simple problem on the face of it, it ends up being a confusion point for majority of amateur programmers starting to learn coding.
Check out the video below to see the most common mistakes committed by students while writing code for Prime numbers!!
