Prime Number Check: flowchart, algorithm and program
This program reads a number n and prints whether it is prime. It tries divisors starting from 2 and stops once i * i goes past n, because a factor larger than the square root would need a matching factor smaller than it.
▶ Watch the dry run step by step →
Algorithm
- Step 1: Start.
- Step 2: Set isPrime = 1.
- Step 3: Read n.
- Step 4: If n < 2, go to step 5; otherwise go to step 6.
- Step 5: Set isPrime = 0.
- Step 6: Set i = 2.
- Step 7: If i * i <= n, go to step 8; otherwise go to step 11.
- Step 8: If n % i == 0, go to step 9; otherwise go to step 10.
- Step 9: Set isPrime = 0, break. Go to step 11.
- Step 10: Increase i by 1. Go to step 7.
- Step 11: If isPrime, go to step 12; otherwise go to step 13.
- Step 12: Print n is prime. Go to step 14.
- Step 13: Print n is not prime.
- Step 14: Stop.
Program in C, Python and Java
Prime Number Check program in C
#include <stdio.h>
int main() {
int n, i, isPrime = 1;
printf("Enter n: ");
scanf("%d", &n);
if (n < 2) {
isPrime = 0;
}
for (i = 2; i * i <= n; i++) {
if (n % i == 0) {
isPrime = 0;
break;
}
}
if (isPrime)
printf("%d is prime\n", n);
else
printf("%d is not prime\n", n);
return 0;
}Prime Number Check program in Python
n = int(input("Enter n: "))
isPrime = True
if n < 2:
isPrime = False
i = 2
while i * i <= n:
if n % i == 0:
isPrime = False
break
i += 1
if isPrime:
print(n, "is prime")
else:
print(n, "is not prime")Prime Number Check program in Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n: ");
int n = sc.nextInt();
boolean isPrime = true;
if (n < 2) {
isPrime = false;
}
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
isPrime = false;
break;
}
}
if (isPrime)
System.out.println(n + " is prime");
else
System.out.println(n + " is not prime");
}
}
Sample input: n = 7
Output: 7 is prime
How it works
- Start with isPrime = 1, which means we assume n is prime until we find a reason it is not.
- If n < 2, set isPrime = 0 right away, since 0, 1 and negative numbers are not prime. The loop condition i * i <= n is already false for these values, so the loop does not run.
- The loop runs i = 2, 3, 4, ... while i * i <= n. For n = 7 it checks only i = 2 (4 <= 7), then i = 3 gives 9 > 7 and the loop ends.
- Inside the loop, if n % i == 0 then i divides n exactly. We set isPrime = 0 and break, because one divisor is enough to prove n is not prime.
- After the loop, isPrime decides the message: 1 prints 'is prime', 0 prints 'is not prime'. For n = 7 no divisor was found, so it prints '7 is prime'.
Dry run (trace table)
| Step | Line | Box | isPrime | n | i | Output |
|---|---|---|---|---|---|---|
| 1 | 3 | Start | ||||
| 2 | 4 | isPrime = 1 | 1 | |||
| 3 | 6 | Read n | 1 | 7 | Enter n: | |
| 4 | 8 | n < 2? | 1 | 7 | ||
| 5 | 11 | i = 2 | 1 | 7 | 2 | |
| 6 | 11 | i * i <= n? | 1 | 7 | 2 | |
| 7 | 12 | n % i == 0? | 1 | 7 | 2 | |
| 8 | 11 | i++ | 1 | 7 | 3 | |
| 9 | 11 | i * i <= n? | 1 | 7 | 3 | |
| 10 | 18 | isPrime? | 1 | 7 | 3 | |
| 11 | 19 | Print n is prime | 1 | 7 | 3 | 7 is prime |
| 12 | 23 | Stop | 1 | 7 | 3 |
Time and space complexity
Time: O(√n) · Space: O(1). The loop runs at most √n times doing constant work each time, and only a few variables are used.
Common mistakes
- Forgetting the n < 2 check, so 1 (and 0 or negatives) gets reported as prime because no divisor is ever tried.
- Looping all the way to n - 1 instead of stopping at the square root. It still gives the right answer but does far more work than needed.
- Using i < sqrt(n) instead of i * i <= n. This misses perfect squares like 9 or 25, since the divisor equal to the square root is never tested.
Viva questions
Q1. Why is isPrime initialised to 1 and not 0?
We assume n is prime until we find a divisor. The flag is set to 0 only when we find a reason it is not prime, such as n < 2 or a number that divides n evenly.
Q2. What does the condition n < 2 on line 8 do, and what happens for inputs 0, 1 and a negative number?
It marks 0, 1 and all negative numbers as not prime, because a prime must be at least 2. For these inputs the for loop does not run, because i*i = 4 is already greater than n, so isPrime stays 0.
Q3. What does n % i == 0 check, and why do we break after finding it?
It checks whether i divides n exactly, which means n has a divisor other than 1 and itself. One divisor is enough to prove n is not prime, so break stops the loop and saves time.
Q4. Why does the loop run only while i*i <= n instead of up to n-1?
If n = a*b, then one of the two factors must be at most sqrt(n). So if no divisor exists up to sqrt(n), none exists beyond it either. Writing i*i <= n avoids calling sqrt() and floating-point errors.
Q5. Trace the program for n = 2 and n = 9. What is printed?
For n = 2, the loop does not run because 2*2 = 4 > 2, so it prints '2 is prime'. For n = 9, i = 2 gives 9%2 = 1, then i = 3 gives 3*3 = 9 <= 9 and 9%3 = 0, so isPrime becomes 0 and it prints '9 is not prime'.
Q6. What is the time complexity of this program, and how does it compare with checking every i up to n-1?
The worst case is O(sqrt(n)), which happens when n is prime. Checking every i up to n-1 would be O(n), so this version is much faster for large n.
Q7. What would change if you used i <= n/2 or i < n as the loop condition, or if you stepped i by 2 after checking 2?
The result would still be correct, but the loop would do more work: O(n) iterations instead of O(sqrt(n)). Stepping i by 2 after handling 2 separately skips even numbers, which halves the work but is still O(sqrt(n)).
Q8. Can i*i overflow for large n, and how would you fix it?
Yes. For n close to INT_MAX, i*i can exceed the range of int near the end of the loop, which is undefined behaviour. Using long long for i, or testing i <= n/i, avoids this.
Frequently asked questions
Why do we only check divisors up to the square root of n?
If n = a * b, then one of a or b must be at most the square root of n. So if no divisor is found up to the square root, none exists beyond it either.
Is 1 a prime number in this program?
No. A prime must be greater than 1, so the n < 2 check sets isPrime = 0 and the program prints that 1 is not prime.
Why write i * i <= n instead of using sqrt(n)?
It stays in whole-number arithmetic, so there is no need for math.h or worry about floating-point rounding. It also correctly includes the case where i equals the square root, such as i = 3 for n = 9.