Re^7: OT: Finding Factor Closest To Square Root

[BrowserUk]

so it seems inappropriate to take into account the time taken to factorize

Inappropriate maybe, but it's bloody boring waiting for it :)

The other part of the argument against doing the factorising, is I haven't thought of, nor seen, a way to use them, that arrives at the result more quickly.

As the factor you are looking for can be any combination (small c), of the prime factors of N, I haven't seen any algorithm that doesn't require an exhaustive search of those combinations plus trial division to determine if you've found the answer. The result is that the descending, linear search is easier to code and runs more quickly.

I have produced the results for all the integers 1-2 million, and 3-4 million, 10-11 million and 100-101 million and then atttempted to find some sort of pattern to the results. There may be one there, but my meagre memory of numerical analysis is not enough to devine it.

28.x% of of the low ranges are primes. This falls of very slowly as the scale of the range increases, but it's only dropped to 27.76% by the time you get the the 100-101 million range. This is worst case for the linear search. If the factorisation ran more quickly, then it would allow you to skip the search in those cases.

Whether that would result in an overall speed up, given that you would have to factor all the numbers and (so far) fall back to a linear search for those Ns that are not primes, I think is dubious.

As the range gets higher, the frequency of the primes gets less, so the benefit of performing the factorisation reduces as the cost of the linear search increases, but also the cost of the factorisation increase and much more rapidly that the cost of the linear search.

I will install Math::Pari. I think it would be interesting to see if there is any pattern to the prime factors of the factor.

This has probably already been analysed to death sometime, but if it has, I'm not typing in the right keywords to locate it.