# Generate Sieve of Eratosthenes without “sieve” (generate prime set in interval)

How do I generate a list of primes based on the Sieve of Eratosthenes?

I mean by excluding the divisible numbers beforehand, which is tricky for large numbers.

I am an number theory amateur, but was thinking...

It's easy to generate not-even numbers in base 2 (binary): just make a set of natural numbers where the LSD (least significant digit, or LSB - l.s. bit) is 1 (not zero). This is a prime sieve with numbers that 2 divides eliminated.

Now if I wanted to generate numbers that 3 does not divide in base 3: just make a set of natural numbers where the LSD is 1 or 2 (not zero). This is a prime sieve with numbers that 3 divides eliminated.

... for many bases, but let's just consider base 2 and 3 in this example.

Is there a base conversion algorithm or other solution to enable these obvious 'sieve sets' (made-up term) simultaneously - perhaps constructing a number systems that is both obviously divisible by 2 and 3, instead of two number systems (one obviously divisible by 2, another by 3)?

The exhausting part of this to consider I think, if even possible (no pun intended), is converting between bases. i.e. Using, in the naive algorithm, multiplication and subtractions for each digit.

PS: I know it's more efficient to run probabilistic primality test on a random number, i.e. check if it's prime, but I would love the idea of constructing number systems that easily generate sets of primes, ignoring the composites, since the probability that a number is prime decreases logarithmically as 1/ln(x) - i.e. p(# around 1e3) = 14% and p(# around 1e300) = 1%, so mostly wasted memory when initially constructing the sieve of eratosthenes set unless there is a way to skip by number system!

I know this is ridiculous, but can't figure out why it won't work, or how it might. I think it has to do with: https://en.wikipedia.org/wiki/Divisibility_rule#Beyond_30, which requires knowing the prime factors ahead of time, or knowing an algorithm for finding the inverse modulo n (none exists).

• Such a number system or "base" would work just fine, provided you bring the set of "relatively prime" ones digits along for the ride... But this set of ones digits is simply the set of primes in the range $[p+1, p#]$ if the largest prime in the base is $p$, and you are back to using lots of memory... – abiessu Jun 30 '16 at 5:07