Sunday, September 30, 2012

Project Euler Problem 357

Lame Brute Force 103secs @ 3,3ghz
import primefacmodule as pfm, math
def divp(n):
 a=[]
 if pfm.isprime(n+1)==True and pfm.isprime(n/2+(n/(n/2)))==True:
  for x in xrange(2,int(math.sqrt(n))+1):
   if n%x==0:
    if pfm.isprime(x+(n/x))==True:
     a.append(x)
    else: 
     return False
  
  for x in xrange(0,len(a)): #check other divisors
   z=(n/a[x])+(n/(n/a[x]))
   if pfm.isprime(z)==True:
    pass
   else:
    return False
  return True # every divisor brings a prime
 else:
  return False

l=[1,6]
p=pfm.primesbelow(100000000) # numbers are prime-1

for x in p:
 b=int(str(x-1)[::-1][::len(str(x-1))]) #last digit
 if b==0 or b==2 or b==8:
  if divp(x-1)==True:
   l.append(x-1)

print sum(l)

No comments:

Post a Comment