Previously we have read how to find prime number using C code, here we will learn how to find the all prime number up to n.
A prime number is a positive natural number, whose value greater than 1 and it has only two factors 1 and the number itself. Either you can say that prime numbers only divided by itself and 1.
There are many ways to find all prime numbers up to n. In this blog post, we will discuss the Trial division method and the Sieve of Eratosthenes algorithm.
Let us see an example to understand the sentence “prime numbers up to n”.
Suppose a given number is n, the task is to print all prime numbers up to n. So if the user enters 10 then the output will be 2,3,5,7.
Trial Division Method
Example 1.
It is the simplest way to find the all prime numbers of an integer n. In this method, we are using two loops outer and nested. The outer loop is used to produce the numbers up to “n” and the nested loop is used to check the numbers for the prime number. If any of the numbers are prime then nested loop print this number.
#include<stdio.h>
int main(int argc, char *argv[])
{
int iRetValue = 0;
int iNumber = 0;
int iLoop =0;
int iLoopin =0;
int iLimit =0;
int iPrimeFlag = 0;
printf("Enter the number : ");
scanf("%d",&iNumber);
if( iNumber <= 1)
{
printf("\n\nEnter a Valid number\n");
return 0;
}
else
{
//outer loop to create the number
for(iLoop=2 ; iLoop <= iNumber; iLoop++)
{
iPrimeFlag = 0; // Assign value to flag
// Calculate the limit for nested loop
iLimit = iLoop/2;
for(iLoopin = 2; iLoopin <= iLimit; iLoopin++)
{
// Check prime number
if((iLoop % iLoopin) == 0)
{
iPrimeFlag = 1;
break;
}
}
if(iPrimeFlag == 0) //Print if number is prime
{
printf("\n %d is a prime number..\n", iLoop);
}
}
}
return 0;
}
Output of the program
Example 2.
In this method, we are using a loop and function to find all prime numbers of an integer. The loop is used to create numbers up to n and function is used to check the number prime or not. If the number is a prime number then the function return “1” either its returns “0”.
#include <stdio.h>
#define PRIME_NUMBER 1
int IsPrimeNumber(int iNumber)
{
int iLoop = 0;
int iPrimeFlag = 1;
//Divide the number by 2
int iLimit = iNumber/2;
for(iLoop = 2; iLoop <= iLimit; iLoop++)
{
if((iNumber % iLoop) == 0) // Check prime number
{
iPrimeFlag = 0;
break;
}
}
return iPrimeFlag;
}
int main(int argc, char *argv[])
{
int iRetValue = 0;
int iNumber = 0;
int iLoop =0;
printf("Enter the number : ");
scanf("%d",&iNumber);
if( iNumber <= 1)
{
printf("\n\nEnter a Valid number\n");
return 0;
}
else
{
for(iLoop=2 ; iLoop <= iNumber; iLoop++)
{
iRetValue = IsPrimeNumber(iLoop);
//Check Prime Number
if (iRetValue == PRIME_NUMBER)
{
printf("\n%d is prime number..\n", iLoop);
}
}
}
return 0;
}
Output of the above program
If you want to learn more about c language, here free trial c video course for you.
Find all the prime numbers less than or equal to a given integer n by Eratosthenes method
- First create a list of consecutive integers numbers from 2 to n: (2, 3, 4, …, n).
- Initially, let q equal 2, the smallest prime number.
- Find the all multiple of q by counting to n from 2q in increments of q, and mark them on the list. (these will be 2q, 3q, 4q, …; the q itself should not be marked).
- Find the first number greater than q in the list that is not marked. If there was no such number, stop. Otherwise, let q now equal this new number (which is the next prime), and repeat from step 3.
When the algorithm terminates, the numbers remaining not marked in the list are all the primes below n.
Algorithms of Sieve of Eratosthenes
Input: an integer n > 1
Let A be an array of Boolean values, indexed by integers 2 to n,
initially, all set to true.
for i = 2, 3, 4, ..., not exceeding √n:
if A[i] is true:
for j = i2, i2+i, i2+2i, i2+3i, ..., not exceeding n :
A[j] := false
Output: all i for which A[i] is true is the prime number.
Example:
To find all the prime numbers less than or equal to 15, proceed as follows.
- First, create an array of integers from 2 to 15 and initially mark all the elements as a prime number.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 - The first prime number in the list is 2, marked every number in the list, which is multiple of 2.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 - The next unmarked number in the list after 2 is 3, marked every number in the list, which is multiple of 3.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 - The next number not yet marked out in the list after 3 is 5, but 5*5 is greater than 15. So here we will stop the process because all members have been marked out at this point.
Note: All unmarked numbers in the list are prime numbers.
C program to find all prime number up to n
#include <stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
void GetRangeOfPrimeNumber(const int n, char *pcRangePrimeNum)
{
int aIndex = 0;
//Set pcRangePrimeNum 1 from pcRangePrimeNum[0..n]
memset(pcRangePrimeNum, 1,(n+1));
pcRangePrimeNum[0] = 0;
pcRangePrimeNum[1] = 0;
int iLimit = sqrt(n);
for (aIndex=2; aIndex <= iLimit; aIndex++)
{
// If pcRangePrimeNum[aIndex] is not changed, then it is a prime
if (pcRangePrimeNum[aIndex] == 1)
{
int i;
// Update all multiples of p
for (i=aIndex*2; i<=n; i += aIndex)
{
pcRangePrimeNum[i] = 0;
}
}
}
}
// Driver Program to test above function
int main()
{
int n =0;
int iPrimeNumber =0;
char *pcPrimeNumber = NULL;
printf("Enter the number: ");
scanf("%d",&n);
if(n <= 1)
{
printf("\n\nIt is not a prime number\n\n");
return 0;
}
else
{
// Allocate memory for list
pcPrimeNumber = malloc(sizeof(char)*(n+1));
//Get the prime numbers
GetRangeOfPrimeNumber(n,pcPrimeNumber);
printf("\n\nThere are following prime numbers smaller than or equal to \n\n" );
// Print all the prime numbers
for (iPrimeNumber=2; iPrimeNumber<=n; iPrimeNumber++)
{
if (pcPrimeNumber[iPrimeNumber])
{
printf("prime %d\n",iPrimeNumber);
}
}
free(pcPrimeNumber); // free the allocated memory
}
return 0;
}
Output of the program:
Recommended Articles for you:
- Find the prime number using the C program.
- find all prime numbers up to n using trial division and Sieve of Eratosthenes algorithm.
- Check date validity in C?
- How to use if in C programming.
- How to use C if-else condition?
- Create an employee record system in C.
- Way to create a library management system in C.
- How to create student record system in C?
- How to use for loop in C?
- You should know while loop use.
- When we should use do while in the C program.
- Use of the switch case in the C program.
- C language character set.
- Elements of C Language.
- Data type in C language.
- Operators with Precedence and Associativity.
- How to pass an array as a parameter?
- Memory Layout in C.
- File handling in C, In a few hours.
- Replacing nested switches with the multi-dimensional array
- How to access a two-dimensional array using pointers?
- Brief Introduction of switch case in C.
- 100 C interview Questions.
- Function pointer in c, a detailed guide.
- How to use the structure of function pointer in c language?
- Function pointer in structure.
- Pointer Arithmetic in C.
- Brief Introduction of void pointer in C.
References:
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
3 comments