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).
If you want to eliminate multiples of 2 and 3, just work in base 6=2x3. The only possible primes are those that end in 1 or 5.
Similarly, to sieve out numbers with all factors 2, 3, 5, and 7, work in base 2x3x5x7 = 210.
This is standard stuff for those developing sieves, and there are many advanced takes on this.
Read, play around, have fun, and don't get upset if what you find isn't new. The important thing is to find stuff by yourself.