[cfoley]

So, I'm working through project euler and a sieving techniques are useful for a lot of the problems. However, I don't know how big to make the sieves. I used to just make them of length one million. It was fast enough and they usually (maybe always) contained the correct answer.

But a fixed size sieve is a big assumption that I'm not happy with. A pragmatic solution is to start with a sieve of length 10 and when that's not big enough, multiply the length by 10 and so on until we can find the answer.

This satisfies my inner software engineer but not my inner mathematician. I know I can't calculate the optimum size of sieve (if I could, I wouldn't need the sieve at all) but there must be some techniques for finding an upper bound.

In case an example is helpful, how about Euler 47? My top lever function looked like this. Posting any more would spoil the problem:

	def findStreak(self, size):
		listLength = 10
		while(True):
			factors = self.sieveForFactors(listLength)
			streakStart = self.findStreakInList(factors, size)
			if streakStart != -1:
				return streakStart
			listLength *= 10

[CTphpnwb]

First, I have to say that I think the solution given on that link for 3 consecutive numbers is wrong:

Quote

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

The prime factors do not include 2². That is 4 and it's not a prime. The prime factors of 644 are 2, 2, 7, and 23. Therefore 644 has four prime factors and they're not all unique when compared to 646. (Ok, you could say they're 2, 7, and 23 so only 3 factors, but they're still not all unique.)

That said, the prime factors of any number are all less than or equal to its square root.

This post has been edited by CTphpnwb: 31 August 2014 - 01:28 PM

[macosxnerd101]

What the question is really asking is this: Let x, x + 1, x + 2, x + 3 be consecutive integers. For each such integer y, consider the set Factors = { p : p|y and p is prime}. We are considering the cardinality of this set. So in this sense, there are three distinct prime factors.

[cfoley]

Yeah, I misunderstood to begin with too. In this case distinct means that duplicates should be eliminated from the factorisation.

[jon.kiparsky]

cfoley, on 31 August 2014 - 10:43 AM, said:

But a fixed size sieve is a big assumption that I'm not happy with. A pragmatic solution is to start with a sieve of length 10 and when that's not big enough, multiply the length by 10 and so on until we can find the answer.

My stock prime-search approach (in python at least) is to maintain a list of primes, and append primes to it as I find them. I then "sieve" by walking up the list until I hit p >sqrt(n). This allows me to generate arbitrary numbers of primes, and the language deals with the length of my "sieve" for me.

This is a good way to get large lists of primes to play with. I'm not sure how it stacks up to other methods for speed - it's nicely flexible, and works well for euler-sized problems, so I'm okay with it.