C Exercises: Find the prime numbers which are less than or equal to a given integer

C Basic Declarations and Expressions: Exercise-136 with Solution

Write a C program to find the prime numbers which are less than or equal to a given integer.

Input:
n (1 <= n <= 999,999)

Sample Solution:

C Code:

#include <stdio.h>
#define MAX_N 999999
int is_prime[MAX_N + 1];
int prime[MAX_N];

int main() {
  int p = 0, i, j, n;

  printf("Input a number:\n");
  scanf("%d", & n);

  for (i = 0; i <= n; i++)
    is_prime[i] = 1;
  is_prime[0] = is_prime[1] = 0;
  for (i = 2; i <= n; i++) {
    if (is_prime[i]) {
      prime[p++] = i;
      for (j = 2 * i; j <= n; j += i)
        is_prime[j] = 0;
    }
  }
  printf("Number of prime numbers which are less than or equal to %d ", n);
  printf("\n%d", p);
  return 0;
}

Sample Output:

Input a number:
123
Number of prime numbers which are less than or equal to 123
30

Flowchart:

C programming Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a C program which reads an integer n and find the number of combinations of a, b, c and d (0 <= a, b, c, d <= 9) where (a + b + c + d) will be equal to n.
Next: Write a C program to check if a point (x, y) is within a triangle or not. The triangle has formed by three points.