|
|
|
| Perl-Sensitive Sunglasses | |
| PerlMonks |
Re^2: OT: Finding Factor Closest To Square Rootby QM (Parson) |
| on Feb 20, 2005 at 07:20 UTC ( [id://432845]=note: print w/replies, xml ) | Need Help?? |
|
Yes, but this still takes a long time for large prime N, as it has to count down from sqrt(N) to 1.
It would go twice as fast if we checked N%2==0. It would go six times as fast if we checked for N%3==0 also. Perhaps using GCD(N,sqrt(N)#) (where N# is the primorial of N) would improve the situation? The problem then becomes one of generating all primes upto sqrt(N), where we could cheat and just have a big list precomputed. ...Better yet, would a quick test of N for primality solve the problem of prime N? -QM
In Section
Seekers of Perl Wisdom
|
|
||||||||||||||||||||||