0

I know that there are many prime generators, such as the sieve of Eratosthenes or Atkin. But they generate numbers sequentially, starting from the small ones. What method can I use to get prime numbers in an interval without starting from the smallers?

An option could be to use a random number generator and test the output with a primality test, deterministic or probabilistic, depending of what I want to achieve. Anyway the test would be slow and complex.

Is there any quick and easy method to generate primes non consecutively? A pseudoprime generator would also be OK.

regards

I rewrite the question more clearly:

How can I generate prime numbers in a given interval without: - going sequentially from the smallers to the largest ones (as with a Erathostenes Sieve) - nor using slow probabilistic primality tests on a random sequence?

Is there any FAST and EASY algorithm or function that generates numbers in such a way that if you run it for a long time you get all prime numbers on an interval? (I don't mind if it also generates some composites).

skan
  • 7,423
  • 14
  • 59
  • 96
  • possible duplicate of [Random prime number](http://stackoverflow.com/questions/1769680/random-prime-number) – Peter O. Mar 28 '13 at 03:34
  • so is it just one prime, or sequential primes in an interval?? You do mention "interval", it's a bit unclear. If it's several primes in an interval, you do benefit from a sieve. – Will Ness Mar 28 '13 at 11:15
  • (contd.) that's an "offset" sieve, which first sieves up to the sqrt of the top limit of your interval, then sieves the interval itself, like a segmented sieve that jumps to the designated segment. So ***which is it***?? – Will Ness Mar 28 '13 at 11:29
  • I mean a way to generate "pseudoprimes" on a given interval. But I don't want to generate all numbers of increasing size and later test its primality. Imagine I wanted to generate random odd numers instead. I could use some kind of modular polynomia to generate numbers x, and then calculate 2X+1. That would give me odd numbers of any size on the interval without first calculate all the small ones. I want something similar but for "pseudoprimes". A generator that given enough time generates all prime numbers in an interval, but if it generate some (few) non prime ones it's also OK. – skan Mar 28 '13 at 12:15
  • My post is not a duplicate of that one because he wants strictly prime numbers, and of a fixed size and he accepts to get them from the smaller to the largest, calculating all and then sieving. I don't need all, just some kind of function that generate numbers probably primes on a given interval . – skan Mar 28 '13 at 12:18
  • "some kind of modular polynomia to generate numbers x" **Why**? You know, you can always generate the odds sequentially on an interval `[a,b]` as `o,o+2,o+4, ... b` where `o = (a|1)`. **Is it essential** for you that the numbers are generated in some **"random" order?** Also, no testing is involved in sieving (by Eratosthenes method that is). But it does produce the primes in order. (and it must first find the smaller primes, but only up to the square root of the upper bound, `b`). There's also no "calculating all" numbers in interval first, just array allocation. – Will Ness Mar 28 '13 at 15:00
  • Hi Will, I meant a modular polynomia or iterator to calculate random numbers, not odd numbers. – skan Mar 28 '13 at 19:33

1 Answers1

0

If the interval is not too big and the low end of the interval is not too high, you can use a segmented Sieve of Eratosthenes; the definitions of "too big" and "too high" depend on your aspirations and your patience, but anything bigger than about 10^15 is unlikely to be successful. Otherwise you can pick a random odd number in the desired interval, test it for primality, and either keep it if it is prime or try the next larger odd number, continuing until you find a prime; you could speed that up if you wish by using a prime wheel to generate candidate primes rather than just testing the next odd number. There is no third choice.

You've said that you don't mind too much if the number is composite. In that case, you could generate a random odd number, test it just for strong pseudoprimality to base 2 and no other bases, and keep it if the test says it is prime or try again with the next odd number if the test says it is composite. That's not a perfect primality test, but it is faster than doing 25 tests of random bases for a Miller-Rabin test, and faster than a Lucas pseudoprime test, and may be good enough for your purposes.

You can find descriptions of all these things by searching at Stack Overflow, or by looking at my blog, or you can ask here if you have additional specific questions.

user448810
  • 17,381
  • 4
  • 34
  • 59
  • Hi. My intention is to use it to generate numbers of around 200 digits. – skan Mar 28 '13 at 19:30
  • 1
    That's far too big for sieving, so your only choice is generate-and-test: pick an odd number, test if it's prime, try another if it's composite. A 2,3,5,7-wheel will reduce the number of prime candidates by half compared to just adding 2 at each failure. What primality test to use will be determined by how confident of primality you must be: 2-spsp by itself is sufficient for many purposes, or you can add a Lucas pseudoprime test if you want greater confidence. Check my blog or ask specific questions if you need more help. – user448810 Mar 28 '13 at 19:51
  • Thanks. I've also heard of the 2PRP method, quite fast – skan Mar 29 '13 at 00:19