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).
