[Go] solution_2 can someone elaborate?

[jdemchuk]

GoPrime solution_2 is genius, but I could use some help understanding how it works on the base algorithm. Anyone able to comment? It's about 2X faster than my own Go code, following Dave's C++ example.

func (s Sieve) RunSieve() {
	var factor, start, step uint64
	end := (s.size + 1) / 2
	q := uint64(math.Sqrt(float64(s.size)) / 2)

	for factor = 1; factor <= q; factor++ {
		if (s.bits[factor/8] & bits.RotateLeft8(1, int(factor))) != 0 {
			continue
		}

		start = 2 * (factor*factor + factor)
		step = factor*2 + 1

		for ; start < end; start += step {
			s.bits[start/8] |= bits.RotateLeft8(1, int(start))
		}
	}
}

How is q, the square root of the sieve, further divided by 2, able to work? Most of the other algorithms don't do this.
This solution_2 does some inverse logic, starting with all bits = 0, and then flipping the ones representing non-primes to 1.
It's very good, if a little hard to interpret.

[ssovest]

Hello. Factor and q represent indices, not numbers themselves. This allows the program not to store even numbers and not to convert a number to its index on every assignment. And inverse logic is there just because Go initialises all elements to 0, so it would be a waste of resources to re-initialize the whole array to 0xff.

[jdemchuk]

Thanks! This makes sense, and definitely provides a performance improvement, which could also be generalized to work in other languages.