Having floated this boat, here's a sieve method for
obtaining all numbers of divisors for integers from
1 to n:
dsieve =: 3 : 0
s =. <.>:i.n=.y
d =. n#1
p =. 2
while. p < %:n do.
pp =. 1
np =. (<.n%p)<.<.p^npl =. <.p^.n
q =. np#0
pl =. p^i.npl+1
NB. get q = powers of prime p
NB. eg q for p=3 is 1 1 2 1 1 2 1 1 3 ...
while. pp<n do.
q =. q+np$1{.~-pp
pp =. <.pp*p
end.
NB. q =. +/@:((+/) ($(1{.~-) )"0 ]) pl NB. slower than the explicit loop
q =. q$~<.n%p
i =. I.mask =. n$1{.~ - p
s =. (<. (mask#s) % q{pl) i } s
d =. ((mask#d) * q + 1) i } d
p =. 4 p: p NB. or could search for next non-1 in }.s
end.
d * >:s>1
)
timer'#dsieve 1000000'
+-----+-------+
|1.446|1000000|
+-----+-------+
Pari GP does this in about 1.2 seconds, so a reasonable
comparison.
Thanks,
Mike
On 22/10/2014 00:15, 'Pascal Jasmin' via Programming wrote:
a complication with the approach is:
*/ 2 2 2 3 3 5 5 7 11
138600
d */ 2 2 2 3 3 5 5 7 11
144
and so for the ranges starting at 38600 to 63320 there is a greater maximum,
and it also appears that for some multiples of 138600, the number of divisors
exceeds (for part of the range) of multiples of 83160
a number that simplifies the process is:
*/ 2 2 2 3 5 7 11
9240
as it allows needing to examine with d only multiples of it.
----- Original Message -----
From: Raul Miller <[email protected]>
To: Programming forum <[email protected]>
Cc:
Sent: Tuesday, October 21, 2014 6:41 PM
Subject: Re: [Jprogramming] An easy Euler Project one (485)
See also http://oeis.org/A002182
Also Roger Hui's point about a sieve is probably a good one since this
problem only needs you to consider prime factors less than 10000. Still,
those 1229 prime factors multiplied by the 1e8 limit means we would need
something on the order of several terabytes of memory for intermediate
results if we were to store the entire sieve in the obvious way. So some
extra work would be needed, and I'm not sure how that would pan out.
---
This email is free from viruses and malware because avast! Antivirus protection
is active.
http://www.avast.com
-----
No virus found in this message.
Checked by AVG - www.avg.com
Version: 2014.0.4765 / Virus Database: 4040/8432 - Release Date: 10/22/14
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
