C program to print all prime numbers from 1 to n

Category: C Program

Learn how to print all prime numbers from 1 to n using C. This article provides a detailed explanation and a complete C program to find and print prime numbers efficiently.

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 -

C program to check if a number is prime number

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.