Oct-01-2021, 06:39 AM
Basically, given a number n, print all primes smaller than or equal to n. It is also given that n is a small number.
A prime number is a number that is divisible by only two numbers – themselves and 1
Example:
Input: n =10
Output: 2 3 5 7
Explanation: Only 4 prime numbers are there which are less than or equal to 10
The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so. Following is the algorithm to find all the prime numbers less than or equal to a given integer n by the Eratosthenes method:
Ref - https://www.interviewbit.com/blog/sieve-...tosthenes/
When the algorithm terminates, all the numbers in the list that are not marked are prime.
Firstly write all the numbers from 2,3,4…. n
Now take the first prime number and mark all its multiples as visited.
Now when you move forward take another number that is unvisited yet and then follow the same step-2 with that number.
All numbers in the list left unmarked when the algorithm ends are referred to as prime numbers.
A prime number is a number that is divisible by only two numbers – themselves and 1
Example:
Input: n =10
Output: 2 3 5 7
Explanation: Only 4 prime numbers are there which are less than or equal to 10
The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so. Following is the algorithm to find all the prime numbers less than or equal to a given integer n by the Eratosthenes method:
Ref - https://www.interviewbit.com/blog/sieve-...tosthenes/
When the algorithm terminates, all the numbers in the list that are not marked are prime.
Firstly write all the numbers from 2,3,4…. n
Now take the first prime number and mark all its multiples as visited.
Now when you move forward take another number that is unvisited yet and then follow the same step-2 with that number.
All numbers in the list left unmarked when the algorithm ends are referred to as prime numbers.