# An algorithm based on Eratosthenes Sieve

1. Dec 4, 2005

### alejandrito

Modify the Eratosthenes Sieve to count the number of all divisors of the given number. Find an algorithm which for given number N <= 10000 will create a field of N numbers such that the value of the i-th element of the field is the number of all divisors of the number i for each i <= N, but the solution mustn´t be worse than O(n.log n).
I don´t have any idea how to proceed if I should satisfy the given maximal difficulty. Can anybody give me some hint? Thank you.

2. Dec 4, 2005

### Hurkyl

Staff Emeritus
It's usually a good idea to simply try and solve the problem first, and then worry about how efficient is.

Do you know how to solve the problem with any algorithm?

3. Dec 5, 2005

### alejandrito

Ok... if I proceed according to Eratosthenes (so I start in 2 and below each multiple of 2 i make some sign and do this whith each prime p_k <= n without any simplification, finally the number of signs at i-th position will be the number of all divisors of i). This algorithm has the effecienty O(n/2 + n/3 + n/5 + .... n/p_k) where p_k is the maximal prime less or equal as n. The estimation of this could be n(SUM of 1/p_j) <= n*(number of all primes <= n) < 6n/ln(n) which results enough or not? I don´t really know and also I´ve used one very strong mathematical estimation so this seems to me very strange..I've obtained a hint that I should use the simplification of Eratosthenes Sieve that works in time O(n.log n), but I don´t know this simplification and also I cannot find it. So I think that this approach without any simplification doesn´t solve the problem. That´s what I have found about it. And also you´re right in that I´m beginner in programming. Generally I´m very confused... it´s enough or not?

Last edited: Dec 5, 2005
4. Dec 5, 2005

### Hurkyl

Staff Emeritus
An estimate, not the estimate. :tongue2: And I think you dropped the "n*" -- shouldn't that be 6n²/ln(n)?

1 is a lot bigger than $1/p_j$, so it seems plausible that this is an overestimate. Do you know anything about sums of reciprocals of things?

Last edited: Dec 5, 2005
5. Dec 5, 2005

### alejandrito

I think that the estimation established by n/8 ln n < PI(n) < 6n/ln n is correct (which results form the work of Chebyshev, he also prooved that there are better constants than 1/8 and 6 in the estimations like a previous and I really believe in it) and is is also coppied from one manual (I am not saying that everything in it must be correct but I think that this inequality is)

Do you know anything about sums of reciprocals of things? It´s very general question I may know something... but maybe I still cannot see what do you want to tell me.... maybe we can estimate it using another way SUM(1/p_j) <= SUM(1/i, i:=2 to n) < log n which can be very easily prooved by the graphical aproach (SUM(1/i, i:=2 to n) < INTEGRATE from 1 to N (dx / x) = log n. You think that this suffices to me?

6. Dec 5, 2005

### Hurkyl

Staff Emeritus
That I believe.

But remember that your expression was n*PI(n), and the upper bound on that would be n*(6n/ln n)

It sure sounds like it proves $n \sum_j 1/p_j < n \ln n$?

This particular sum: $\sum_{i = 1}^n 1/i \in \Theta(\ln n)$ is a good one to remember.

7. Dec 5, 2005

### Hurkyl

Staff Emeritus
That I believe.

But remember that your expression was n*PI(n), and the upper bound on that would be n*(6n/ln n)

It sure sounds like it proves $n \sum_j 1/p_j < n \ln n$.

This particular asymptotic, $\sum_{i = 1}^n 1/i \in \Theta(\ln n)$, is a good one to remember.