14972Re: [PrimeNumbers] Sieve for twin primes
- Jun 12, 2004Andreas Ernst wrote:
> Some people noted, that the url I gave was notI'm sorry but your methods are well-known.
> valid. Please try to access the ps file on a sieve
> for twin primes via my homepage
> You find the ps file in the section 'Hobbies'.
All primes above 3 are on the form 6n+/-1. You use this with a wheel of size 6
to avoid numbers divisible by 2 or 3. That is common. Larger wheels, e.g. of
size 5# = 30 to also avoid numbers divisible by 5, are more efficient in many
Your second idea is to represent the potential twin 6n+/-1 with a single bit
representing n instead of 2 bits, one for each of the 2 numbers. This is also a
very common technique when searching a set of 2 or more simultaneous primes. If
a set of m primes is required, m=2 for twin primes, then each sieve prime p runs
through m loops to strike out n for which the i'th number (1<=i<=m) in the m-set
is divisible by p.
Jens Kruse Andersen
- << Previous post in topic