Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

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

by QM (Parson)
on Feb 20, 2005 at 07:20 UTC ( #432845=note: print w/replies, xml ) Need Help??


in reply to Re: OT: Finding Factor Closest To Square Root
in thread OT: Finding Factor Closest To Square Root

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
--
Quantum Mechanics: The dreams stuff is made of

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://432845]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others rifling through the Monastery: (2)
As of 2022-09-30 00:54 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer my indexes to start at:




    Results (125 votes). Check out past polls.

    Notices?