Home / C / Loop / C Program to Display All the Prime Numbers up to N

C Program to Display All the Prime Numbers up to N

in ,
Prime number

C program to display all primes up to $n$ has been shown here. Here $n$ is a positive integer. For example if $n = 20$, we get all the prime numbers less or equal to $20$ i.e. $2, 3, 5, 7, 11, 13, 17, 19$. The algorithm, pseudocode and time complexity of the program have been shown below.






1. Algorithm to display all primes up to N


1. Take input of a positive number n as limit.

2. Repeat step 3 to 5, for each i $\in$ [2, $n$]

3. Check for each j $\in$ [2, $\sqrt{i}$], if i is divisible by any value of j

4. If step 3 is true for atleast one j, then i is not a prime.

5. If step 3 is false for each i, then display i as a prime




2. Pseudocode to display all primes up to N


Input : A postive number $n$ as limit

Output : All the prime number below $n$

1. Procedure checkPrime($n$):

2. Repeat for $i \in [2, n]$:

3. $flag \leftarrow 0$

4. Repeat for $j \in [2, \sqrt{i}]$:

5. If $i \mod j$ == 0:

6. $flag \leftarrow 1$

7. break

8. If $flag == 0$:

9. Print $i$

10. End Procedure





3. Time complexity to display all primes up to N


Time Complexity: O(n$\sqrt{n}$)

Where n is the total count of positive numbers and O($\sqrt{n}$) is the time to check primality of each number.





4. C Program & output to display all primes up to N

Code has been copied
/*************************
    alphabetacoder.com
C program to find all the 
prime numbers up to n 
**************************/

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

int main() {
    // declare variables
    int n, i, j, flag = 0;

    // take input of the limit
    printf("Enter the limit = ");
    scanf("%d", & n);

    printf("List of primes upto %d: ", n);
    // consider each number from i = 2
    // to n for primality test
    for (i = 2; i <= n; i++) {
        // initialize variable
        flag = 0;

        //check if current i is prime or not
        //If i has divisor between 2 and
        // square root of i, then 
        // i is not prime else i is prime
        for (j = 2; j <= sqrt(i); j++) {
            if (i % j == 0) {
                flag = 1; // mark as not prime
                break; // exit from loop
            }
        }
        // flag = 0 means i is prime.
        // Display i
        if (flag == 0)
            printf("%d ", i);
    }

    return 0;
}

Output

Case 1:

Enter the limit = 50

List of primes upto 50: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47


Case 2:

Enter the limit = 100

List of primes upto 100: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97





Labels: ,