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
- Step 1: Start.
- Step 2: Read n.
- Step 3: Print heading.
- Step 4: Set i = 2.
- Step 5: If i <= n, go to step 6; otherwise go to step 14.
- Step 6: Set isPrime = 1, j = 2.
- Step 7: If j * j <= i, go to step 8; otherwise go to step 11.
- Step 8: If i % j == 0, go to step 9; otherwise go to step 10.
- Step 9: Set isPrime = 0 (break). Go to step 11.
- Step 10: Increase j by 1. Go to step 7.
- Step 11: If isPrime == 1, go to step 12; otherwise go to step 13.
- Step 12: Print i.
- Step 13: Increase i by 1. Go to step 5.
- Step 14: Print newline.
- 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)
| Step | Line | Box | n | i | isPrime | j | Output |
|---|---|---|---|---|---|---|---|
| 1 | 3 | Start | |||||
| 2 | 6 | Read n | 20 | ||||
| 3 | 7 | Print heading | 20 | Prime numbers from 2 to 20: | |||
| 4 | 8 | i = 2 | 20 | 2 | |||
| 5 | 8 | i <= n? | 20 | 2 | |||
| 6 | 9 | isPrime = 1, j = 2 | 20 | 2 | 1 | 2 | |
| 7 | 10 | j * j <= i? | 20 | 2 | 1 | 2 | |
| 8 | 16 | isPrime == 1? | 20 | 2 | 1 | 2 | |
| 9 | 17 | Print i | 20 | 2 | 1 | 2 | 2 |
| 10 | 8 | i++ | 20 | 3 | 1 | 2 | |
| 11 | 8 | i <= n? | 20 | 3 | 1 | 2 | |
| 12 | 9 | isPrime = 1, j = 2 | 20 | 3 | 1 | 2 | |
| 13 | 10 | j * j <= i? | 20 | 3 | 1 | 2 | |
| 14 | 16 | isPrime == 1? | 20 | 3 | 1 | 2 | |
| 15 | 17 | Print i | 20 | 3 | 1 | 2 | 3 |
| 16 | 8 | i++ | 20 | 4 | 1 | 2 | |
| 17 | 8 | i <= n? | 20 | 4 | 1 | 2 | |
| 18 | 9 | isPrime = 1, j = 2 | 20 | 4 | 1 | 2 | |
| 19 | 10 | j * j <= i? | 20 | 4 | 1 | 2 | |
| 20 | 11 | i % j == 0? | 20 | 4 | 1 | 2 |
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.