How to find all prime numbers up to n using trial division and Sieve of Eratosthenes algorithm

find all prime number in c

A prime number is a positive natural number, whose value greater than 1 and has only two factors 1 and the number itself. In another word prime number only divided by itself and 1.

In this article, we will read, how to find the all prime number up to n. There are several methods to find the all prime number but here, I will discuss the Trial Division method and Sieve of Eratosthenes algorithm.

For Example,

If the user enters the 10, then all prime number up to 10 is 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 is prime then nested loop print this number.

OutPut of the program

aticleworld.com

 

 

prime number up to n

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”.

OutPut of the above program

Prime number up to n

 

Prime number up to n

If you want to learn more 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

  1. First create a list of consecutive integers numbers from 2 to n: (2, 3, 4, …, n).
  2. Initially, let q equal 2, the smallest prime number.
  3. 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).
  4. 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.

https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

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.

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 element 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 the 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 the 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 member have been marked out at this point.

Note: All unmarked number in the list are prime numbers.

C program to find all prime number up to n

OutPut of the program

prime number upto n

 

 




References:
https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

One comment

Leave a Reply