On Sat, Mar 21, 2020 at 04:18:32PM +0000, Jonathan Fine wrote: > Hi > > In https://bugs.python.org/issue40028 <https://bugs.python.org/issue40028?>, > Ross Rhodes suggested adding to the standard library a function that finds > the prime factors of a non-negative integer. So far as I know, any general > algorithm for doing this requires a list of prime numbers.
No, that's incorrect. Having a precomputed list of prime numbers is impractical for heavy-duty factorization of even moderately largish numbers, let alone genuinely large numbers, although trial division by the first few primes is often useful to eliminate the easy cases. But trying to hold onto a table of millions of primes is wasteful and most importantly unnecessary. Primes can be cheaply generated on the fly, as needed, and probably faster than they can be read off a hard drive: https://primes.utm.edu/notes/faq/LongestList.html There are 16,352,460,426,841,680,446,427,399 primes below `10**27` https://oeis.org/A006880 so even if we used a table of compact 32-bit integers, rather than int objects, that would take over 50 thousand million petabytes of storage if my calculations are correct. There may be more compact ways to store it, but I doubt you could get it under a few million petabytes. And 10**27 is not an especially large number. It has only 27 digits. `(2*17*31*101*157*199)**100` has over 900 digits, and sympy can factorise it effectively instantly, without needing to pre-compute a multiple petabyte table of primes :-) (In fairness, I did kinda cheat by generating a number I knew was easily factorisable. Working on an arbitrary 900+ digit number isn't so fast.) [...] > > Consider > > >>> 2**32 > > 4294967296 > > And if someone needs to find primes of this size, they've > > probably got a spare gigabyte or two. For what it's worth, I just found the above prime factorization on a computer with 145 MB available in my home directory. (I *really* need a new computer.) In your research, you may consider 2**32 to be a large number, but to people working with primes (for fun, or for research), it's tiny. Thousands of digits is getting large; the largest known prime, as of January 2020, has over 24 million digits. -- Steven _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/RJ5XESEZ7K6BUBE4WXBM5JTHWWIOSP2G/ Code of Conduct: http://python.org/psf/codeofconduct/
