Prime Numbers in a Range: flowchart, algorithm and program

This program reads n and prints every prime number from 2 up to n. The outer loop picks each number i, and the inner loop checks whether any j from 2 up to the square root of i divides it evenly.

▶ Watch the dry run step by step →

Algorithm

  1. Step 1: Start.
  2. Step 2: Read n.
  3. Step 3: Print heading.
  4. Step 4: Set i = 2.
  5. Step 5: If i <= n, go to step 6; otherwise go to step 14.
  6. Step 6: Set isPrime = 1, j = 2.
  7. Step 7: If j * j <= i, go to step 8; otherwise go to step 11.
  8. Step 8: If i % j == 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 j by 1. Go to step 7.
  11. Step 11: If isPrime == 1, go to step 12; otherwise go to step 13.
  12. Step 12: Print i.
  13. Step 13: Increase i by 1. Go to step 5.
  14. Step 14: Print newline.
  15. Step 15: Stop.

Program in C, Python and Java

Prime Numbers in a Range program in C

#include <stdio.h>

int main() {
    int n, i, j, isPrime;
    printf("Enter n: ");
    scanf("%d", &n);
    printf("Prime numbers from 2 to %d:\n", n);
    for (i = 2; i <= n; i++) {
        isPrime = 1;
        for (j = 2; j * j <= i; j++) {
            if (i % j == 0) {
                isPrime = 0;
                break;
            }
        }
        if (isPrime) {
            printf("%d ", i);
        }
    }
    printf("\n");
    return 0;
}

Prime Numbers in a Range program in Python

n = int(input("Enter n: "))
print("Prime numbers from 2 to", n, ":")
for i in range(2, n + 1):
    isPrime = True
    j = 2
    while j * j <= i:
        if i % j == 0:
            isPrime = False
            break
        j += 1
    if isPrime:
        print(i, end=" ")
print()

Prime Numbers in a Range 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();
        System.out.println("Prime numbers from 2 to " + n + ":");
        for (int i = 2; i <= n; i++) {
            boolean isPrime = true;
            for (int j = 2; j * j <= i; j++) {
                if (i % j == 0) {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime) {
                System.out.print(i + " ");
            }
        }
        System.out.println();
    }
}

Sample input: n = 20
Output: Prime numbers from 2 to 20: 2 3 5 7 11 13 17 19

How it works

  • The outer loop runs i from 2 to n. Each i is a candidate that we test for being prime.
  • Before testing, isPrime is set to 1, which means we assume i is prime until we find a divisor.
  • The inner loop runs j from 2 while j * j <= i. If i has a divisor, at least one divisor is at most the square root of i, so we don't need to check beyond that.
  • If i % j == 0, then j divides i. We set isPrime = 0 and break out of the inner loop, since one divisor is enough.
  • After the inner loop, if isPrime is still 1, we print i. For n = 20 this gives 2 3 5 7 11 13 17 19.
  • For i = 2 and i = 3 the inner loop doesn't run at all (2*2 > 2 and 2*2 > 3), so isPrime stays 1 and they are correctly printed as primes.

Dry run (trace table)

StepLineBoxniisPrimejOutput
13Start
26Read n20
37Print heading20Prime numbers from 2 to 20:
48i = 2202
58i <= n?202
69isPrime = 1, j = 220212
710j * j <= i?20212
816isPrime == 1?20212
917Print i202122
108i++20312
118i <= n?20312
129isPrime = 1, j = 220312
1310j * j <= i?20312
1416isPrime == 1?20312
1517Print i203123
168i++20412
178i <= n?20412
189isPrime = 1, j = 220412
1910j * j <= i?20412
2011i % j == 0?20412

Time and space complexity

Time: O(n√n) · Space: O(1). The outer loop runs n times and the inner loop runs at most √i times for each i, using only a few variables.

Common mistakes

  • Forgetting to reset isPrime = 1 inside the outer loop. If it is set only once before the loop, one composite number makes every later number look non-prime.
  • Starting the outer loop at 1. The number 1 is not prime, but the inner loop would not run for it, so it would be printed wrongly. Start at 2.
  • Writing j <= i or j < i in the inner loop. That still works but does far more checks than needed. Also, if you use j * j <= i, don't swap it for j <= sqrt(i) without including math.h and handling float rounding.

Viva questions

Q1. Why is isPrime set to 1 at the start of each iteration of the outer loop (line 9)?

We assume every number is prime until we find a divisor. It must be reset for each i, otherwise a 0 left over from a previous composite number would make all later numbers look non-prime.

Q2. Why does the outer loop start at i = 2 and not at 0 or 1?

0 and 1 are not prime by definition. 2 is the smallest prime, so we start checking from there.

Q3. What does the condition i % j == 0 on line 11 check, and why do we break after setting isPrime = 0?

It checks whether j divides i exactly, with no remainder. If it does, i is composite, so there is no need to test other divisors and break exits the inner loop early.

Q4. Why does the inner loop run only while j * j <= i instead of up to i - 1?

If i has a divisor larger than its square root, it must also have a matching divisor smaller than the square root. So if no divisor is found up to sqrt(i), none exists, and this saves a lot of work.

Q5. How does the program handle i = 2 and i = 3? The inner loop seems not to run for them.

For i = 2 and 3, j = 2 gives j*j = 4, which is greater than i, so the inner loop body never runs. isPrime stays 1 and they are correctly printed as primes.

Q6. What is printed if the user enters n = 1, 0 or a negative number?

The outer loop condition i <= n is false at the start, so nothing is checked. Only the header line and a blank line are printed, which is correct since there are no primes in that range.

Q7. What is the time complexity of this program?

For each i the inner loop runs at most about sqrt(i) times, so the total is roughly O(n * sqrt(n)) or O(n^1.5).

Q8. What would change if you wrote j <= i / 2 instead of j * j <= i, or used the Sieve of Eratosthenes?

With j <= i / 2 the output stays the same but it is slower, since the work per number grows from sqrt(i) to i/2. The Sieve of Eratosthenes would cut the time to about O(n log log n), at the cost of O(n) extra memory for a boolean array.

Frequently asked questions

Why does the inner loop stop at j * j <= i?

If i = a * b, then one of a or b must be at most the square root of i. So if no number up to the square root divides i, nothing larger will either, and i is prime.

Why do we use break when a divisor is found?

Once one divisor is found, i is already known to be not prime. Break stops the inner loop early and saves unnecessary checks.

Is 1 a prime number, and what does this program do for n = 1?

No, 1 is not prime. For n = 1 the outer loop starts at 2 and never runs, so the program prints only the heading and an empty line.

More programs

← All programs

Try AI Flowchart free →