Hello guys, today, we are going to discuss one of the most common programming exercises for beginners is, write a program to check if a given number is prime or not? There are many ways to check if a number is prime or not, but the most common of them is the trial division, which is what we will see in this tutorial. In my opinion, these kinds of programs are their first steps towards algorithmic understanding. You first come up with a solution, which is driven by the fact that prime numbers are natural numbers, that are not divisible by any positive number other than 1 and themselves. Then, you write a for loop to check every number, starting from 1 to a given number, to see if the given number is divisible by any positive number or not. This leads you to the solution.
Then you find some more the fact that there is no need to check till N-1, where N is the number we are checking for primeness, and checking till the square root of N is enough. This reduces a lot of time, especially while checking a large number is prime or not.
Further, you come to know that if it's not divisible by 2, then there is no need to checking for any other even number, and you increment the counter by 2 instead of 1. So in a way, you learn how to optimize your solution by taking advantage of the facts available.
After this, you can try something like the Fibonacci series or maybe finding factorial of a number in Java to do some more practice on programming. This will not only teach you language basics like loops, control statements like if-else, use of arithmetic, and relational operator but also helps to develop programming logic.
By the way, you can even take this problem of checking if a number is prime or not, to the next level, by trying to implement different algorithms for finding primes like the sieve of Atkin or sieve of Eratosthenes. In fact, in programming challenges, you often need to build your prime number cache up to a specific number to progress further in finding a solution.
Then you find some more the fact that there is no need to check till N-1, where N is the number we are checking for primeness, and checking till the square root of N is enough. This reduces a lot of time, especially while checking a large number is prime or not.
Further, you come to know that if it's not divisible by 2, then there is no need to checking for any other even number, and you increment the counter by 2 instead of 1. So in a way, you learn how to optimize your solution by taking advantage of the facts available.
After this, you can try something like the Fibonacci series or maybe finding factorial of a number in Java to do some more practice on programming. This will not only teach you language basics like loops, control statements like if-else, use of arithmetic, and relational operator but also helps to develop programming logic.
By the way, you can even take this problem of checking if a number is prime or not, to the next level, by trying to implement different algorithms for finding primes like the sieve of Atkin or sieve of Eratosthenes. In fact, in programming challenges, you often need to build your prime number cache up to a specific number to progress further in finding a solution.
Prime Number Checker in Java
And, here is the complete Java program to check if a given number is prime or not. This question is also asked on written tests and interviews as to how to print prime numbers from 1 to 100 or finding the prime factor of a number in Java.
#include <stdio.h>
int main() {
int n, i, flag = 0;
printf("Enter a positive integer: ");
scanf("%d", &n);
for (i = 2; i <= n / 2; ++i) {
// if n is divisible by i, then n is not prime
// change flag to 1 for non-prime number
if (n % i == 0) {
flag = 1;
break;
}
}
// 0 and 1 are not prime numbers
if (n == 0 || n == 1) {
printf("%d is neither prime nor composite.", n);
}
else {
// flag is 0 for prime numbers
if (flag == 0)
printf("%d is a prime number.", n);
else
printf("%d is not a prime number.", n);
}
return 0;
}
That's all in this program about how to check if a number is prime or not. The number must be an integer, as the concept of prime is only for natural numbers and not for floating-point numbers. As I said, there are a couple of more algorithms for checking if a number is prime or not, and some of the algorithms are optimized for finding prime numbers.