Anonymous user
Talk:Zumkeller numbers: Difference between revisions
→Why this limitation in c++
m (→Why this limitation in c++: changing d.size gets the right solution) |
|||
Line 51:
return true;</lang>
:Your program is limited to 31 divisors.<BR>I'm testing mostly in the web on TIO.RUN like TIO.RUN/#cpp-gcc to be comparable. d.size >30 takes more than 60s limit :-(<br> [[User:Horsth|Horsth]] ([[User talk:Horsth|talk]]) 06:41, 12 May 2021 (UTC)
Alright, so I'm not seeing any overflow here. the variable d points to a vector of unsigned ints, stored in an array, so d.size() can become extremely large. I think the largest set I saw was 88 divisors, and the sum did not overflow. I also am still not seeing the bad outputs you did, so I'm not sure what's going on there, except for 99504. I use the condition odd|n divisors > 24 but I don't think that holds for large N if N is even. 99504 may be the first number that gets through. Given the problem description I didn't anticipate large even numbers to be evaluated; they get filtered before printing to console anyhow, so I think I wrote it that way for efficiency. I really don't remember. If you remove that condition the output looks fine through the first 100 000, but it will take a very long time. Probably, if you want to improve on this, there are a few handy properties of the sequence that could be used to bring time complexity down. But really, changing the data structure for d to make insertion faster and working with base 2 throughout instead of converting for no good reason would really speed up computation time. And there are lots of places to trade space for time, too.
--[[User:Mckann|Mckann]] ([[User talk:Mckann|talk]]) 23:38, 12 May 2021 (UTC)
| |||