Kulwinder Kaurkulwinder3213

The sieve of Eratosthenes algorithm is an ancient algorithm that is used to find all the prime numbers less than given number T. It can be done using O(n*log(log(n))) operations. Using this algorithm we can eliminate all the numbers which are not prime and those that are less than given T. Also, we will traverse from 2 to the root of the given number ( √T ).

There will not exist any factor of T greater than ( √T ). Suppose x and y are the factors of T. In that case, x*y = T . Hence, at least one or both should be <=√ T, so we need to traverse until ( <=√ T ) only.

Finding all prime numbers using **brute force** will required **O(n3 )**

**method 1:** allPrimeBruteForce(T)

```
1
2
3
```

```
for i = 2 to T
if isPrime(i) print(i)
End
```

**method 2:** isPrime( n )

```
1
2
3
4
```

```
for i = 2 to n / 2
if (n % i == 0) return true
End
return false;
```

Generate numbers from 2 to T (2 is the smallest prime).

Traverse from smallest prime number which is num = 2.

Eliminate or mark all the multiples of num (as 0 or -1) which are lesser than or equal to T. It will help remove non-prime numbers and will help to reduce our number of comparisons to check for each number.

Update the value of num to the immediate next prime number. The next prime is the next (non

**0 or -1**) number in the list which is greater than the current number (num).Repeat step three until

**num<=√T**.

Traverse the whole list and number print. All the numbers (>=0) will be our required prime numbers lesser than T (given number).

Print all prime numbers less than 15.

Create list = 2,3,4,5,6,7,8,9,10,11,12,13,14,15

num=2.

traverse from 2 to √15.

num =2. Remove all multiples of 2 then list= [ 2,3,0,5,0,7,0,9,0,11,0,13,0,15 ]

num=3, immediate non zero number.

Mark all multiples of 3 then list= [ 2,3,0,5,0,7,0,0,0,11,0,13,0,0 ]

num=5, which is the next prime, but num is not <=√15.

Now we have generated all the prime numbers less than 15. Prime numbers less than 15 are 2, 3, 5, 7, 11, 13.

```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
```

```
boolean list = {
2 to T
}
for i = 2 to <= √T
if (list[i])
then {
for j = i to j * i < N
list[j * i] = false // Eliminate the multiple of i
}
End
//To print Primes
for i = 2 to T
if (list[i])
print(i + 1)
End
```

```
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
```

```
class Solution {
public static void printPrimes(int n) {
if (n <= 2) return;
boolean prime[] = new boolean[n];
Arrays.fill(prime, true);
for (int i = 2; i * i < n; i++) {
if (prime[i]) {
for (int j = i; j * i < n; j++) {
prime[j * i] = false;
}
}
}
int count = 0;
for (int i = 2; i < n; i++) {
if (prime[i])
System.out.print(i + " ");
count++;
if (count % 10 == 0)
System.out.println();
}
}
public static void main(String args[]) {
printPrimes(100);
}
}
```

Time required to eliminate numbers is constant which is

(Equation 1)

Take

**N**common from above equation will be

(Equation 2)

Taking the harmonic progression of prime numbers will be

(Equation 3)

Hence the complexity is O(n*log(log(n)))

Rabin-Karp and Knuth-Morris-Pratt Algorithms
Discuss the article in the forums
The fundamental string searchin...

Read More Discuss this article in the forums
Introduction
I have seen a number of competitors complain that they are ...

Read More Discuss this article in the forums
Introduction
Primality testing of a number is perhaps the most common probl...

Read More