Skip to content

Instantly share code, notes, and snippets.

@jakedobkin
Created December 9, 2011 23:21
Show Gist options
  • Save jakedobkin/1453787 to your computer and use it in GitHub Desktop.
Save jakedobkin/1453787 to your computer and use it in GitHub Desktop.
Euler 47- modified sieve method in python
# 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
@djacobs
Copy link

djacobs commented Dec 10, 2011

# 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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment