Efficient algorithm to find out all prime numbers with in a given limit.
In this section I will explain the
efficient algorithm to find all the prime numbers with in a given
limit.
Before that, below is the glimpse of
Prime Numbers And Composite Numbers.
What is a Prime Number?
A Prime number is an positive integer
greater than one which is divisible only by itself or 1
Example: 2, 3, 5, 7
On the other hand, the numbers that has
at least one divisor other than 1 or itself are called composite
numbers.
Example: 4, 6, 8, 9, 10
Problem:
Find out all prime numbers smaller than
the given integer.
Input: 10
Output: 2, 3, 5, 7
Solution:
The naive approach to solve the problem
is take all numbers lesser than or equal to the given number and
check each number if it is a prime or not. Though this is a
simple approach, if the given limit is quiet large say 1 million,
then doing the prime check for all numbers from 2 to 1000000 will be
not be time efficient.
We can solve
this problem efficiently by applying the Sieve of Eratosthenes algorithm.
Algorithm:(Let N be the given input
limit):
Step 1: Create an array of Boolean with
size N+1. This array will represent Primeness of all numbers from 2
to N.
Step 2: Take P=2 as initial value
Step 3: Multiply P with numbers
starting from 2, 3, 4 and so on.. and mark the corresponding index in
the array as not prime.
Step 4: Increment P by 1 and Continue
Step 3 and 4 until P < Square Root(N)
Step 5: In the final array the indexes
which are not marked are the prime numbers
Code in Java:
---------------------------------------------------
public
class
Prime {
public
static
void
findPrimes(int
num) {
boolean[]
allNums = new
boolean[num
+ 1];
for
(int
i = 2; i <= Math.sqrt(num); i++)
{
if
(!allNums[i]) {
for
(int
j = 2; num >= i * j; j++) {
allNums[i
* j] = true;
}
}
}
for
(int
i = 2; i < allNums.length;
i++) {
if
(!allNums[i]) {
System.out.print(i
+ " ");
}
}
}
public
static
void
main(String[] args) {
findPrimes(48);
}
}
---------------------------------------------------
Sample Input: 50
Output: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47
