Active3 years, 4 months ago
Divisors of numbers We'd like to generate a table of divisors and sums of divisors of all the numbers up to at least 120. So we need everyone to contribute at least three or four rows to the table. Download this file, then open and edit it as you would any text file (use Notepad or something like that). In mathematics, and specifically in number theory, a divisor function is an arithmetic function related to the divisors of an integer.When referred to as the divisor function, it counts the number of divisors of an integer (including 1 and the number itself). It appears in a number of remarkable identities, including relationships on the Riemann zeta function and the Eisenstein series of.
I need to find all divisors of all numbers between 1 and n (including 1 and n). where n equals 10^6 and I want to store them in the vector.
This is too much time taking as well. Can i optimize it in any way?
hasan18.5k88 gold badges5353 silver badges8484 bronze badges
vivek sehgalvivek sehgal
4 Answers
this runs in
O(N*log(N))
Intuition is that upper N/2 numbers are run only once. Then from remaining numbers upper half are run once more ...
Other way around. If you increase N from lets say 10^6 to 10^7, than you have as many opertions as at 10^6 times 10. (that is linear), but what is extra are numbers from 10^6 to 10^7 that doesnt run more than 10 times each at worst.
number of operaions is
this becomes then
N * sum(1/n for n from 1 to N)
and this is N*log(N)
that can be shown using integration of 1/x over dx from 1 to N
We can see that algorhitm is optimal, because there is as many operation as is number of divisors. Size of result or total number of divisors is same as complexity of algorhitm.
Luka RahneLuka Rahne8,84722 gold badges2727 silver badges5454 bronze badges
I think this might not be the best solution, but it is much better than the one presented, so here we go:
Go over all the numbers (
i
) from 1
to n
, and for each number: - Add the number to the list of itself.
- Set multiplier to 2.
- Add
i
to the list ofi * multiplier
. - increase
multiplier
. - Repeat steps 3 & 4 until
i * multiplier
is greater thann
.
1,79422 gold badges1616 silver badges2525 bronze badges
[Edit3] complete reedit
Your current approach is
O(n^1.5)
not O(n^2)
Originally I suggested to see Why are my nested for loops taking so long to compute?
Table Of Divisors Worksheet
But as Oliver Charlesworth suggested to me to read About Vectors growth That should not be much of an issue here (also the measurements confirmed it).
So no need to preallocating of memroy for the list (it would just waste memory and due to CACHE barriers even lower the overall performance at least on mine setup).
So how to optimize?
- either lower the constant time so the runtime is better of your iteration (even with worse complexity)
- or lower the complexity so much that overhead is not bigger to actually have some speedup
I would start with SoF (Sieve of Eratosthenes)
But instead setting number as divisible I would add currently iterated sieve to the number divisor list. This should be
O(n^2)
but with much lower overhead (no divisions and fully parallelisable) if coded right.- start computing SoF for all numbers
i=2,3,4,5,...,n-1
- for each number
x
you hit do not update SoF table (you do not need it). Instead add the iterated sievei
to the divisor list ofx
. Something like:
C++ source:
- This took
1.739
s and found13969984
divisors total, max240
divisors per number (including1
andx
). As you can see it does not use any divisions. and the divisors are sorted ascending. List<int>
is dynamic list of integers template (something like yourvector<>
)
You can adapt this to your kind of iteration so you can check up to
nn=sqrt(n)
and add 2 divisors per iteration that is O(n^1.5*log(n))
with different constant time (overhead) a bit slower due to single division need and duplicity check (log(n)
with high base) so you need to measure if it speeds things up or not on my setup is this way slower (~2.383
s even if it is with better complexity).Next thing is to use direct memory access (not sure you can do that with
vector<>
) my list is capable of such thing do not confuse it with hardware DMA this is just avoidance of array range checking. This speeds up the constant overhead of the duplicity check and the result time is [1.793s]
which is a little bit slower then the raw SoF O(n^2)
version. So if you got bigger n
this would be the way.[Notes]
If you want to do prime decomposition then iterate
i
only through primes (in that case you need the SoF table) ...If you got problems with the SoF or primes look at Prime numbers by Eratosthenes quicker sequential than concurrently? for some additional ideas on this
Community♦
SpektreSpektre33k66 gold badges5555 silver badges235235 bronze badges
Another optimization is not to use -vector- nor -list- , but a large array of divisors, see http://oeis.org/A027750
First step: Sieve of number of divisors
Second step: Sieve of divisors with the total number of divisors
Note: A maximum of 20-fold time increase for 10-fold range. --> O(N*log(N))
Dev-C++ 5.11 , in C
With some results:
StackPCStackPC