C, C++ Program to Print Prime Numbers between 1 to N using Sieve Algorithm

Write a C, C++ program to print prime number between 1 to N.  C, C++ Program to print prime numbers between 1 to 10. In this program, we take an input value of n and our program will print prime numbers between 1 to n.

This type of questions are mostly asked during viva or in interviews.

In this post, You are going to learn most efficient algorithm to generate prime numbers Sieve of Eratosthenes algorithm for to generate prime numbers between 1 to N.

Interview Questions

Program to check whether entered number is prime or not

Sieve of Eratosthenes Algorithm for Generating Prime Numbers

Let's first understand how this algorithm works. Suppose we have to find prime numbers between 1 to 15.

 Step 1 : Generate number from 2 to 15.

 2   3   4   5   6   7   8   9   10   11   12   13   14   15

 Step 2:  2 is the first element in the list. Strike out it's multiple.

2   3   4   5   6   7   8   9   10   11   12   13   14   15


Step 3:  3 is the next element in the list. Strike out it's multiple.

2   3   4   5   6   7   8   9   10   11   12   13   14   15

So at the  end,  The element which is left  is prime numbers.

So the prime numbers between 1 to 15 is  2   3   5  7  11  13

C Program to Print Prime Numbers between 1 to N

#include <stdio.h>

int main() {
 
 int num, i, k=2;
 
 printf("Enter number \n");
 scanf("%d",&num);

  //Declare an array
  int prime[num];
 
 /*Generate number 1 to n and marked as zero. */

 for(i=2;i<=num;i++){
  
      prime[i]=0;
 }
 
 
 while(k <= sqrt(num)){
 
    /* Marked multiple of number as 1.*/
 
    for(i = 2; num >= k*i; i++){
   
       prime[k*i] = 1;
    }
    k++;
 }
 
 for(i=2;i<=num;i++){
  
  /* Number marked left as zero is a prime number.*/
  if(prime[i] == 0){
   printf("%d\n",i);
  }
 }
 return 0;
}

C++ Program to Generate Prime Numbers between 1 to N

#include <iostream>
#include <math.h>

using namespace std;

int main() {
 
    int num, i, k=2;
 
    cout << "Enter number \n";
    cin  >>  num;

    //Declare an array
    int prime[num];
 
    /*Generate number from 1 to n and marked as zero. */

    for(i=2; i<=num; i++){
  
       prime[i]=0;
    }
 
 
    while(k <= sqrt(num)){
 
       /* Marked multiple of number as 1.*/
 
       for(i = 2; num >= k*i; i++){
   
          prime[k*i] = 1;
        }
        k++;
    }
 
   for(i = 2; i <= num; i++){
  
      /* Number marked left as zero is a prime number.*/
      if(prime[i] == 0) {
        cout << i << "\n";
       }
    }
 
 return 0;
}

Programming question on Arrays

Programming question on Linked List

Sorting algorithm and their time complexity

Stack implementation

Programming questions using Recursion

C, C++ interview questions

Programming Books

Popular Data Structure Books