**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.

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

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

6.

7.

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

/************************* 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

## No comments:

## Post a Comment

If you have any doubts or suggestions, please leave a note.