Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #7325
| From | Gregory Ewing <greg.ewing@canterbury.ac.nz> |
|---|---|
| Newsgroups | comp.lang.python |
| Subject | Re: Any Better logic for this problem.. |
| Date | 2011-06-10 10:39 +1200 |
| Message-ID | <95d0drFa9jU1@mid.individual.net> (permalink) |
| References | <BANLkTinWq5pjX2+0OVRvm1Xs7ESmYf0qcw@mail.gmail.com> <BANLkTimicVsm7EGMsVu0bXRsa7714MKpwA@mail.gmail.com> <mailman.48.1307611509.11593.python-list@python.org> |
Chris Angelico wrote: > Rather than find all prime numbers up to num, stop at sqrt(num) - it's > not possible to have any prime factors larger than that. That's not quite true -- the prime factors of 26 are 2 and 13, and 13 is clearly greater than sqrt(26). However, once you've divided out all the primes up to sqrt(n), whatever is left, if greater than 1, must itself be prime, so you can add it to your prime factors and stop. -- Greg
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: Any Better logic for this problem.. Chris Angelico <rosuav@gmail.com> - 2011-06-09 19:25 +1000
Re: Any Better logic for this problem.. Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2011-06-10 10:39 +1200
Re: Any Better logic for this problem.. Chris Angelico <rosuav@gmail.com> - 2011-06-10 08:44 +1000
csiph-web