C program to print all prime numbers from 1 to n

Finding all prime numbers between 1 and a given number n is a common programming challenge and an essential concept in number theory. This article will guide you through writing a C program to print all prime numbers in this range.

Introduction

Prime numbers are natural numbers greater than 1 that have no divisors other than 1 and themselves. Printing all prime numbers between 1 and n is a fundamental task that can be achieved efficiently with the right approach.

Prime Number Concept

A number p is considered prime if it is only divisible by 1 and itself. For example, 2, 3, 5, and 7 are prime numbers, whereas 4, 6, 8, and 9 are not.

To check if a number is prime number or not check this article -

Method to Find Prime Numbers

To find all prime numbers between 1 and n, we can use a nested loop approach:

1. Loop through each number from 2 to n.
2. For each number, check if it is divisible by any number from 2 to the square root of that number.
3. It is prime if the number is not divisible by any of these.

This method is efficient because it reduces the number of checks needed to determine if a number is prime.

Write a C program to print all prime numbers from 1 to n

Here is a C program to print all prime numbers between 1 and n:

#include <stdio.h>
#include <math.h>

int main() {
    int n, i, j, isPrime;

    // Taking input from the user
    printf("Enter a positive integer: ");
    scanf("%d", &n);

    printf("Prime numbers between 1 and %d are: ", n);

    // Loop through each number from 2 to n
    for (i = 2; i <= n; i++) {
        isPrime = 1; // Assume the number is prime

        // Check if i is divisible by any number from 2 to sqrt(i)
        for (j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                isPrime = 0; // i is not prime
                break;
            }
        }

        // If isPrime is still 1, then i is a prime number
        if (isPrime) {
            printf("%d ", i);
        }
    }

    return 0;
}

Output

Enter a positive integer: 10
Prime numbers between 1 and 10 are: 2 3 5 7

Explanation of the Code

1. Input: The program takes an integer input n from the user.
2. Outer Loop: The outer loop iterates from 2 to n. Each number in this range is checked for primality.
3. Assumption: The variable isPrime is initially set to 1, assuming the current number i is prime.
4. Inner Loop: The inner loop checks if i is divisible by any number from 2 to the square root of i. If i is divisible by any of these numbers, isPrime is set to 0 (indicating that i is not prime), and the loop breaks.
5. Prime Check: After the inner loop, if isPrime is still 1, the number i is printed as a prime number.

Why Check Up to √i?

Checking up to the square root of i reduces the number of iterations significantly, improving the algorithm's efficiency. This is because if i is divisible by a number larger than its square root, it must also be divisible by a number smaller than its square root.