Danqing Li - 950121-C669 Robert Grzelka - 911009-T437
In the basic programming course (at least on Physics dept.) there has been a programming assignment where you generate all primes between 2..n. One simple way of doing it is to use Eratosthenes sieve:
- create an array 2..n filled with “true” booleans.
- traverse the array and change all (elements whose indexes are) multiples of 2 to false,
- traverse once more and change all multiples of 3 to false,
- then multiples of 5 and so on up till n.
- the primes corresponds to the true values left in the array.
This naive solution takes O(n2) time. The solution can be improved in several ways. It's for instance enough to:
- try primes up to sqrt(n) instead of to n
- and if you are marking multiples of 7 it's enough to start from 7^2 = 49
- because all multiples between 7 and 49 must be marked already.
An algorithm for the problem could look like this:
prime: array [1..n] of boolean = all true
for p in 2..sqrt(n) loop
if prime[p] then
m = p*p
while m <= n loop
prime[m] = false
m = m+p
end loop
end if
end loop
Tip: It's simpler to analyse if you rewrite the while loop to a for loop, then it's a double sum isn't it? How to handle the statement: "if prime(p)" in worst case?
prime: array [1..n] of boolean = all true
for p in 2..sqrt(n) loop
if prime[p] then
for m = p*p; m<=n; m=m+p
prime[m] = false
end loop
end if
end loop
A trivial upper bound is
Analyse the program and determine it's complexity and show that it infact is better. (Use uniform cost criteria)
You should set up the sums and solve them. Don't forget to motivate what you do.
Analysis:
- Outer loop iterates from 2 to sqrt(n), so its simple
$O(sqrt(n))$ - Inner loop iterates with some case for ie. n = 200:
- p = 2 ::: m = [ 4, 6, 8, 10, 12, 14, 16, 18, 20, .... , 194, 196, 198, 200, ] ---> j=99, k=99
- p = 3 ::: m = [ 9, 12, 15, 18, 21, 24, 27, 30, 33, ...., 195, 198 ] ---> j=64, k=163
- p = 4 ::: m = [ ] ---> j=0, k=163
- p = 5 ::: m = [ 25, 30, 35, 40, 45, 50, 55, 60, ...., 190, 195, 200 ] ---> j=36, k=199
- p = 6 ::: m = [ ] ---> j=0, k=199
- p = 7 ::: m = [ 49, 56, 63, 70, 77, 84, 91, 98, ...., 175, 182, 189, 196 ] ---> j=22, k=221
- p = 8 ::: m = [ ] ---> j=0, k=221
- p = 9 ::: m = [ ] ---> j=0, k=221
- p = 10 ::: m = [ ] ---> j=0, k=221
- p = 11 ::: m = [ 121, 132, 143, 154, 165, 176, 187, 198, ] ---> j=8, k=229
- p = 12 ::: m = [ ] ---> j=0, k=229
- p = 13 ::: m = [ 169, 182, 195, ] ---> j=3, k=232
- p = 14 ::: m = [ ] ---> j=0, k=232
- with total number of (outer+inner) iterations: k = 232
In inner loop we see biggest number of iterations for p=2 at first case. Then it will drop almost by p, so complexity would be
We need to find out how many times we add p to m until its
$$ m = pp + jp \leq n \Rightarrow p*(p + j) = n $$
then
and in converting to sum notation
We also notice that:
$$
\sum_{j=m}^n 1 = n + 1 - j = n + 1 - m
$$
so our inner sum will transform to:
$$
\sum_{m=p}^{\frac{n}{p}}1 = \frac{n}{p}+1-p
$$
Then our double sum equation becomes:
$$
\sum_{p=2}^{\sqrt{n}}\left(\frac{n}{p}+1-p\right)
$$
That we split on 3 parts:
$$
\sum_{p=2}^{\sqrt{n}}\frac{n}{p} + \sum_{p=2}^{\sqrt{n}} 1 - \sum_{p=2}^{\sqrt{n}}p
$$
With