C program to find all prime numbers in a range:
In this post, we will write a program to find all prime numbers in a given range or it will find all the prime numbers between 1 and N, where N will be a user-given number. The program will ask the user to enter the value of N and it will print all numbers between 1 to N.
With this program, you will learn how to check if a number is prime or not, and how to use a loop to find all prime numbers in a given range.
Prime number:
A number is called a prime number if it is divisible by 1 and the number itself. For example, 7 is a prime number but 8 is not. Note that 1 is not a prime number. The first prime number is 2. It is also the only even prime number because all other even numbers are divisible by 2.
Algorithm to check if a number is prime or not:
To check if a number is prime or not, we have to use a loop. The loop will check for all numbers starting from 2. If it finds any value that can divide the number, it will not be a prime number. Else, it will be a prime number.
We can iterate from 2 to number - 1. We can also iterate from 2 to number/2 to reduce the number of iteration. Because no number greater than number/2 can divide the number. Similarly, we can further optimize it to iterate from 2 to square root of number. Let’s write down programs for all these ways.
Method 1: C program to find all prime numbers between 1 to N:
In this method, we will use a loop to iterate from 2 to number - 1 to check if a number is prime or not. Below is the complete program:
#include <stdio.h>
int isPrime(int no)
{
if (no == 1)
{
return 0;
}
for (int i = 2; i < no; i++)
{
if (no % i == 0)
{
return 0;
}
}
return 1;
}
int main()
{
int N;
printf("Enter the value of N: ");
scanf("%d", &N);
printf("Prime numbers between 1 to %d: ", N);
for (int i = 2; i <= N; i++)
{
if (isPrime(i))
{
printf("%d ", i);
}
}
}Here,
- N is a variable to hold the upper limit of the range. It asks the user to enter the value of N, and stores the value in N.
- The for loop prints the prime numbers between 1 to N. Since 1 is not a prime number, the loop starts from 2.
- The isPrime method checks if the current value of i is prime or not. If yes, it prints the value of i.
- The isPrime method takes one number as its parameter and checks if that number is prime or not. It returns 0 if it is not a prime number. Else, it returns 1.
- If the number is 1, it returns 0.
- It runs one loop from i = 2 to i = number - 1. On each iteration, it checks if the number is divisible by i or not. If it is divisible, it returns 0 i.e. it is not a prime number. Once the loop ends, it returns 1, i.e. it is a prime number.
If you run this program, it will print output as like below:
Enter the value of N: 100
Prime numbers between 1 to 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
Enter the value of N: 10
Prime numbers between 1 to 10: 2 3 5 7Method 2: C program to find all prime numbers between 1 to N by iterating to number/2:
We can iterate from 2 to number/2 to check if a number is prime or not. Let’s change the isPrime method of the above example to run the loop from 2 to number/2:
#include <stdio.h>
int isPrime(int no)
{
if (no == 1)
{
return 0;
}
for (int i = 2; i <= no/2; i++)
{
if (no % i == 0)
{
return 0;
}
}
return 1;
}
int main()
{
int N;
printf("Enter the value of N: ");
scanf("%d", &N);
printf("Prime numbers between 1 to %d: ", N);
for (int i = 2; i <= N; i++)
{
if (isPrime(i))
{
printf("%d ", i);
}
}
}If you run this program, it will give a similar output.
Method 3: C program to find all prime numbers between 1 to N by iterating to square root of number:
Let’s reduce the number of iteration further. Instead of iterating to number/2, we can also iterate up to square root of the number to check if a number is prime or not. Below is the complete program:
#include <stdio.h>
#include <math.h>
int isPrime(int no)
{
if (no == 1)
{
return 0;
}
for (int i = 2; i <= sqrt(no); i++)
{
if (no % i == 0)
{
return 0;
}
}
return 1;
}
int main()
{
int N;
printf("Enter the value of N: ");
scanf("%d", &N);
printf("Prime numbers between 1 to %d: ", N);
for (int i = 2; i <= N; i++)
{
if (isPrime(i))
{
printf("%d ", i);
}
}
}This program uses the sqrt method to find the square root of a number. This method is defined in the math.h header file. It will print similar result.
You might also like:
- 4 different ways to print the natural numbers in reverse order in C
- C program to find the first and the last digits of a number
- C program to find the sum of digits of a number
- 2 different C programs to draw a butterfly pattern
- 2 different C programs to find the volume and surface area of a cylinder
- 2 different C programs to print a triangle of prime numbers
- 4 different C programs to check if a number is prime or not