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.
To this issue I've just added https://bugs.python.org/issue40028?#msg364757 which reads: A pre-computed table of primes might be better. Of course, how long should > the table be. There's an infinity of primes. > > Consider > >>> 2**32 > 4294967296 > > This number is approximately 4 * (10**9). According to > https://en.wikipedia.org/wiki/Prime_number_theorem, there are 50,847,534 > primes less than 10**9. So, very roughly, there are 200,000,000 primes less > than 2**32. > > Thus, storing a list of all these prime numbers as 32 bit unsigned > integers would occupy about > >>> 200_000_000 / (1024**3) * 4 > 0.7450580596923828 > or in other words 3/4 gigabytes on disk. > > A binary search into this list, using as starting point the expected > location provided by the prime number theorem, might very well require on > average less than two block reads into the file that holds the prime number > list on disk. And if someone needs to find primes of this size, they've > probably got a spare gigabyte or two. > > I'm naturally inclined to this approach because by mathematical research > involves spending gigahertz days computing tables. I then use the tables to > examine hypotheses. See https://arxiv.org/abs/1011.4269. This involves > subsets of the vertices of the 5-dimensional cube. There are of course > 2**32 such subsets. -- Jonathan
_______________________________________________ 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/SU5EIJ2O3OGPXHZMJ27G5JXSL2KMSAZ5/ Code of Conduct: http://python.org/psf/codeofconduct/
