-1

I am trying to generate Prime numbers in ranges of large numbers (10 digits and above). But seems like whichever library I use it takes a infinite amount a time to generate them.

My code in R

library(numbers)
Primes(1000000000,9999999999)

My Code in Python

[i for i in primerange(1000000000,9999999999)]

Is there a better Library to generate these numbers quickly?

LeoG
  • 683
  • 1
  • 8
  • 22
  • 2
    Generating prime numbers is a difficult math problem that takes computers a long time to solve in any method, that's why its useful in things like encryption. There's optimizations, but there's no easy way around the core difficulty – Ofer Sadan Nov 24 '19 at 08:28
  • 2
    Do some more research. There are even useful Qs and As on this topic here on SO (eg https://stackoverflow.com/questions/13326673/is-there-a-python-library-to-list-primes) and the Internet is awash with libraries, algorithms, implementations, even sites you can download lists of primes from. – High Performance Mark Nov 24 '19 at 11:12
  • Also interesting: https://stackoverflow.com/questions/47005608/finding-all-the-10-digit-prime-numbers-that-have-seven-7-in-a-row-python – JohanC Nov 24 '19 at 11:41
  • 3
    According to oeis there are [404204977](https://oeis.org/A006879) primes with 10 digits. Just reading them from file would take some time. – JohanC Nov 24 '19 at 11:50
  • 1
    Large prime numbers end in 1, 3, 7, 9. You could generate 9 (or more) digits, append one of those four digits and test for primality. There is a lot of information on prime testing available. – rossum Nov 24 '19 at 13:54
  • If you're generating many primes from a range, a variation on the sieve of eratosthenes is an efficient way to generalize the observation of @rossum to many more small primes. – President James K. Polk Nov 24 '19 at 14:18
  • What's your `sympy` setup code? – hpaulj Nov 24 '19 at 17:13
  • Thanks @JonanC, let me check this – LeoG Nov 28 '19 at 04:47

1 Answers1

0

@JohanC makes a good observation. Do you really need all of the primes at once? Generating the "next" prime in this range is fast. If you can use 1 or a few at a time you could do

>>> p = nextprime(1000000000)
>>> while 1:
...     print(p)  # or do what you need to do
...     p = nextprime(p)

this shows

1000000007
1000000009
1000000021
...

If you don't want them to be successive (but don't mind the small likelyihood of repeating a value) you could use

while 1:
    p = nextprime(randint(1000000000,9999999999))
    # do something
smichr
  • 16,948
  • 2
  • 27
  • 34
  • 1
    How's this different from `primerange`? `primerange` is a generator that uses `nextprime`. – hpaulj Nov 24 '19 at 17:17
  • `[i for i in iterator]` will exhaust the iterator, a `while` loop allows you to do something with each output of the iterator as they are generated. – smichr Nov 24 '19 at 19:29