Euler 47- modified sieve method in python

gistfile1.txt

# set up 2 sieves- one is erastosthenes, the other is to track count
n=200000
myPrimes = [True]*(n+1)
myCount = [0]*(n+1)

# sieve, but count each time each composite number is hit during sieve 
for i in range (2,n):
	if myPrimes[i] == True:
		j = 2*i
		while j<=n:
			myPrimes[j]=False
			myCount[j]+=1
			j=j+i

# count up runs of numbers with 4 factors- when you get to 4, stop 
count = 0
for k in range (2,len(myCount)-1):
	if myCount[k]==4:
		count += 1
	else:
		count = 0
	if count == 4:
		print "answer is %r" % (k-3)
		break 

I modified this to allow you to set the range easier- basically it's taking 20m to get the answer, which is 134043. I'm going to try to get that down a bit.

basically the first method was doing too much work- the sieve already contains the data about prime factors for each number up to n- you just have to ask for it. here i'm just tracking the count, but you could also actually have it print factors for each number.

You don't need a true/false sieve AND a counting array. You can just initialize the "counts" to 0 (which is the equivalent of "prime" for the purposes of the sieve). You can count down from n, since we can assume our answer is closer to the upper limit of your query than 0. This shaves ~25% processing time. I also factored away the "break," since that I think it's generally inelegant.

# let's track the count in eratosthenes' sieve
n=200000
myPrimes = [0]*(n+1)

# sieve, but count each time each composite number is hit during sieve 
for i in range (2,n):
    if myPrimes[i] == 0:
        j = 2*i
        while j<=n:
            myPrimes[j] += 1
            j=j+i

# count up runs of numbers with 4 factors- when you get to 4, stop 
count = 0

while not count == 4:
    if myPrimes[n]==4:
        count += 1
        n -= 1
    else:
        count = 0
        n -= 1

print "answer is %r" % (n+1)