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

  1. Step 1: Start.
  2. Step 2: Set isPrime = 1.
  3. Step 3: Read n.
  4. Step 4: If n < 2, go to step 5; otherwise go to step 6.
  5. Step 5: Set isPrime = 0.
  6. Step 6: Set i = 2.
  7. Step 7: If i * i <= n, go to step 8; otherwise go to step 11.
  8. Step 8: If n % i == 0, go to step 9; otherwise go to step 10.
  9. Step 9: Set isPrime = 0, break. Go to step 11.
  10. Step 10: Increase i by 1. Go to step 7.
  11. Step 11: If isPrime, go to step 12; otherwise go to step 13.
  12. Step 12: Print n is prime. Go to step 14.
  13. Step 13: Print n is not prime.
  14. 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)

StepLineBoxisPrimeniOutput
13Start
24isPrime = 11
36Read n17Enter n:
48n < 2?17
511i = 2172
611i * i <= n?172
712n % i == 0?172
811i++173
911i * i <= n?173
1018isPrime?173
1119Print n is prime1737 is prime
1223Stop173

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.

More programs

← All programs

Try AI Flowchart free →