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

Last update on September 19 2025 12:44:52 (UTC/GMT +8 hours)

Find all prime numbers ≤n\leq n≤n

Write a C program to find prime numbers that 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;

  // Prompting the user to input a number
  printf("Input a number:\n");
  scanf("%d", &n);

  // Initializing the is_prime array to all true (1)
  for (i = 0; i <= n; i++)
    is_prime[i] = 1;
  is_prime[0] = is_prime[1] = 0; // 0 and 1 are not prime

  // Finding prime numbers using the Sieve of Eratosthenes algorithm
  for (i = 2; i <= n; i++) {
    if (is_prime[i]) {
      prime[p++] = i; // Storing prime numbers in the prime array
      for (j = 2 * i; j <= n; j += i)
        is_prime[j] = 0; // Marking multiples of a prime as not prime
    }
  }

  // Printing the number of prime numbers and the count
  printf("Number of prime numbers which are less than or equal to %d ", n);
  printf("\n%d", p);

  return 0; // End of the program
}

Sample Output:

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

Flowchart:

For more Practice: Solve these Related Problems:

• Write a C program to implement the Sieve of Eratosthenes and print all primes less than or equal to n.
• Write a C program to iterate through numbers up to n and check for prime status using trial division.
• Write a C program to use recursion to list prime numbers below a given limit n.
• Write a C program to generate primes up to n and store them in an array for later processing.

Go to:

• C Basic Exercises Home ↩
• C Programming Exercises Home ↩

PREV : Count combinations of four digits summing to nnn.
NEXT : Check if a point lies within a triangle.

C programming Code Editor:

Click to Open Editor

Have another way to solve this solution? Contribute your code (and comments) through Disqus.