C Program to Print Prime Numbers From 1 to N
Prime numbers are positive integers greater than 1 that have no divisors other than 1 and themselves. In this article, we will learn to generate and display all prime numbers from 1 to N in C programming language.
Algorithm
- Check every number from 1 to N whether it is prime by using isPrime() function.
- In isPrime() Function,
- Iterate from 2 to n/2 and check if the number is divisible by any of the values other than itself.
- If it is divisible by any number, it means the number is not prime, return false.
- If it is not divisible by any number, it means the number is prime, return true.
- If isPrime() returns true, print the number.
- Else continue.
Program to Print Prime Numbers From 1 to N in C
C
// C program to print Prime numbers till N #include <stdbool.h> #include <stdio.h> // This function is to check // if a given number is prime bool isPrime( int n) { // since 0 and 1 is not prime // number return false. if (n == 1 || n == 0) return false ; // Run a loop from 2 to n/2 for ( int i = 2; i <= n / 2; i++) { // if the number is divisible by i, then n is not a // prime number, otherwise n is prime number. if (n % i == 0) return false ; } return true ; } // Driver code int main() { int N = 50; // check for the every number from 1 to N for ( int i = 1; i <= N; i++) { // check if i (current number) is prime if (isPrime(i)) { printf ( "%d " , i); } } return 0; } |
Output
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
Complexity Analysis
- Time Complexity: O(N2)
- Space Complexity: O(1)
Refer to the complete article Program to print prime numbers from 1 to N for more methods to generate prime numbers.