Structure of the article. First I will explain what does sieve mean. Then I will give you some examples with corresponding java codes and finally some exercises :)
According to
http://www.thefreedictionary.com/sieve , "sieve" means A utensil of wire mesh or closely perforated metal, used for straining, sifting, ricing, or puréeing. Similar to this definition sieve is a method of doing stuff, where you keep rejecting the things that are useless and reducing the space that you are currently looking at.
So much of thing in air, Let us now take an example.
1.
Finding primes upto N.
You have to print all primes upto N.
Method1 : For all the numbers i from 1 to N, check if i is prime or not. If it is a prime, then print it.
Subproblem:
Checking whether a number K is prime.
Solution:
1. For all numbers i from 2 to K-1, check if K is divisible by i (as every number is divisible by 1 and itself). If yes, then not a prime else the number is a prime.
Complexity of this solution : O(K)
2. Note that we do not need to check upto K-1, instead we can very well check upto sqrt(K).
Proof: Let us say a number K = a * b. Note that atleast one of a and b <= sqrt(K) otherwise product of them would exceed K. So check just upto sqrt(K).
3. Either use some probabilistic method for finding whether a number is prime or not.
More on this later. For now see link
http://en.wikipedia.org/wiki/Primality_test
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting
Method 2:
Now here comes the idea of sieve. So initially assume that all numbers are prime. Then you try to sieve/refine your search range by not looking at the entire numbers but at the reduced space. eg. When you find all the numbers which are divisible by 2, You do not look into those again, as they are already not prime. So those numbers are sieved out. Now try for 3,4, upto n.
In other terms, You first try all the numbers which are divisible are 2 (except 2 itself),
Note that all those wont be primes. So you can remove those out of your consideration now. Now try the same for 3,4,...... N. Finally you will end up with only prime numbers.
For understanding the actual thing going on, see the code.
So the code basically sets all the numbers upto N to be prime. Then for every number that is still prime, we set all of its multiples upto N to be non-prime.
import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
static boolean[] isPrime;
public static void sieveOptimized(int N) {
isPrime = new boolean[N + 1];
for (int i = 2; i <= N; i++)
isPrime[i] = true;
for (int i = 2; i * i <= N; i++) {
if (isPrime[i]) {
// For further optimization, You can do instead of j += i, j += (2 * i).
// Proof is left to reader :)
for (int j = i * i; j <= N; j += i)
isPrime[j] = false;
}
}
}
public static void sieve(int N) {
isPrime = new boolean[N + 1];
for (int i = 2; i <= N; i++)
isPrime[i] = true;
for (int i = 2; i <= N; i++) {
if (isPrime[i]) {
for (int j = i + i; j <= N; j += i)
isPrime[j] = false;
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int limit = sc.nextInt();
// call the sieve method
sieveOptimized(limit);
for (int i = 1; i <= limit; i++) {
if (isPrime[i])
System.out.printf("%d ",i);
}
}
}
Now comes the complexity part: Complexity of this code is O(n * logn).
Proof: (This proof comes a lot of times in various algorithms, So pay attention).
For all numbers i going from 2 to n, you need to check all the multiples of i. Note that number of multiples of i upto n are n / i. Hence Expression for the complexity will be written as n / 2 + n / 3 + .. + 1. Take n common out of expression. Now it becomes n * (1 / 2 + ..... + 1/n).
Now as the expression is definitely greater than n. So adding an n to the expression won't have any effect on the complexity, So add n to the expression and now it becomes n * (1 + 1 / 2 + ... + 1/ n). The expression (1 + 1 / 2 + 1 / 3 + ... 1 / n) is harmonic sum and it's bounded by ln(n). Hence overall complexity is O(n * logn)
Proof of harmonic sum:
A simple Proof: Let us integrate 1 / x from 1 to n. (Note that we are doing integration, which means sum of area under the curve 1/x, which is greater than (1 + 1 / 2 + ... + 1 / n). Value of the integral can be found easily. In fact integration of 1/x dx is ln(x).
2. Finding Sum of divisors of numbers upto N.
Now you have to find sum of divisors of all numbers upto N. Here we are not just considering proper divisors(numbers other 1 and itself), we are considering all the divisors. Here you can do something like this.
Here let us say divisorSum[i] denotes sum of divisors of i. Intially value of divisorSum[i] is equal to zero. Then for all the numbers i from 1 to n, We check all the multiples of i (let us say j) and add i to divisorSum[j].
In other words, Start from 1 and for all the numbers which are multiples of 1, increment their sumDiviors by 1.
Now do the same for 2,3, ... N. Note that for a number i, you are doing this adding operation upto N/i times. So the complexity calculation is same as before.
Look the beautifully commented code.
import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int n = sc.nextInt();
int divisorSum[] = new int [n + 1];
// For every number i, You know that 2*i,3*i,4*i upto k*i such that k*i<=n, will have i
// as one of it's divisors, so add that to divisorSum[j]
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j += i) {
divisorSum[j] += i;
}
}
// Complexity of this code is O(n * logn)
// Proof: Expression for the complexity can be written as n / 1 + n / 2 + ... + n / n
// take n common
// n * (1 + 1 / 2 + ..... + 1/n)
// (1 + 1 / 2 + 1 / 3 + ... 1 / n) is harmonic sum and it's bounded by logn.
// A simple Proof: Let us integrate 1 / x from 1 to n.
// (Note that we are doing integration, which means sum of area under the curve 1/x
// which is greater than (1 + 1 / 2 + ... + 1 / n)
// value of integration can be found easily
// as integration of 1/x dx is ln(x)
for (int i = 1; i <= n; i++)
System.out.printf("%d ", divisorSum[i]);
System.out.printf("\n");
}
}
}
3.
Finding No of divisors of numbers upto N.
This is also same as the previous example. Here instead of the storing sum in the array, store the number of divisors and for every multiple of i (say j), In the previous example, you were adding value i to divisorSum[j] , Here just increment the count of noOfDivisior[j] by one.
Code is very easy and hence omitted. Complexity is also same.
4. Sieve for finding euler phi function.
I will denote the euler phi function for a number n by phi(n). phi(n) is defined as follows.
It is count of how many number from 1 to n are coprime(having gcd value 1) to n.
For example phi(6) is 2 as 1,5 are coprime to 6.
Few properties of phi function :
a). phi(p) = p - 1. Where p is prime. All the numbers from 1 to p - 1 are coprime to p.
b). phi(a * b) = phi(a) * phi(b) where a and b are coprime.
c). phi(p^k) = p^k - p^(k - 1). Note that here ^ denotes power. Here all the numbers from 1 to p^k are coprime to p^k except all the multiples of p, which are exactly p^(k -1).
Method for finding:
1. Simple : For all numbers from 1 to n, check if it is coprime to n or not, If yes add that to your answer.
2. Let us say your number is n, which can be denoted as p1^k1 * p2^k2 ..... *p_m*k_m. Note that here p1, p2.... pm are prime. Basically n is written in it's prime representation.
Then phi(n) would be [ p1^k1 - (p1^(k1-1) ) ] * ....... [p_m^k_m - (p_m^(k_m-1) )] . The expression for n can also be written as p1^k1 * p2^k2 * .... * p_m^k_m * (1 - 1/p1) * (1 - 1/p2) .... * (1 - 1/pm).
which is equal to n * (1 - 1/p1) * (1 - 1/p2) .... * (1 - 1/p_m).
See the code for details.
Now Let us calculate value of sieve of all numbers from 1 to N.
