An algorithm based on Eratosthenes Sieve

[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.

 

[Hurkyl]

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?

 

[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?

 

[Hurkyl]

The estimation of this could be n(SUM of 1/p_j) <= n*(number of all primes <= n) < 6n/ln(n)

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?

 

[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 approach (SUM(1/i, i:=2 to n) < INTEGRATE from 1 to N (dx / x) = log n. You think that this suffices to me?

 

[Hurkyl]

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)

That I believe.

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

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 approach (SUM(1/i, i:=2 to n) < INTEGRATE from 1 to N (dx / x) = log n. You think that this suffices to me?

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.

 

[Hurkyl]

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)

That I believe.

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

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 approach (SUM(1/i, i:=2 to n) < INTEGRATE from 1 to N (dx / x) = log n. You think that this suffices to me?

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.