[½»Á÷] Project Euler 46 Å·À­¹¤³Ì 46 Ìâ ÒÑÓÐ4È˲ÎÓë

# -*- coding: cp936 -*-
#Å·À­¹¤³Ì 46 Ìâ
#ÈκÎÒ»¸öÆæºÏÊý¶¼ÄÜд³ÉÒ»¸öËØÊýÓëÒ»¸öƽ·½ÊýµÄ¶þ±¶µÄºÍ,Ñ°ÕÒÆÆÀý
#n=prime+2*m**2
from math import sqrt
def isprime(p):    #ÑéÖ¤ÊÇ·ñËØÊý£¬ËØÊý·µ»Ø±¾Éí£¬ºÏÊý·µ»ØFalse
    k=1
    for i in xrange(2,int(sqrt(p))+1):
        if p%i==0:
            k=0
            return False
            break
    if k:
        return p
n=35
while True:
    killer=1                   #ÉèÖòÂÏëµÄÅжϲÎÊý
    if not isprime(n):         #ÑéÖ¤ÊÇ·ñËØÊý£¬ËØÊýÔònµÝÔö¼ÌÐøÏÂһѭ»·£¬ºÏÊý½øÐÐÏÂÒ»²½ÑéÖ¤
        for m in xrange(1,int(sqrt((n-2)/2)+1)):
            for i in xrange(1,n-1):
                if isprime(i) and n==i+2*m**2:
                    killer=0   #·ûºÏ²ÂÏë
                    break
            if not killer:     #·ûºÏ²ÂÏë
                break
    else:
        n+=2
        continue
    if killer:                 #ÑéÖ¤Íê±Ï£¬²»·ûºÏ²ÂÏ룬¼´Îª½á¹û
        print('the number is:%d')%n
        break
    else:
        n+=2

from math import sqrt
primes = []
n = 3
while True :
  isp = True
  for j in primes :
    if j**2 > n : break
    if n%j == 0 :
      isp = False
      break
  if isp :
    primes.append(n)
  else :
    isf = True
    for j in reversed(primes) :
      it = (n-j)/2
      if it == int(sqrt(it))**2 :
        isf = False
        break
    if isf : break
  n = n + 2
print "The number is",n

      integer p(800)
      j=0;n=1
   1  n=n+2
      do 2 i=1,j
        if(p(i)**2.gt.n) goto 3
   2    if(mod(n,p(i)).eq.0) goto 4
   3  j=j+1
      p(j)=n;goto 1
   4  do 5 i=j,1,-1
        k=(n-p(i))/2
   5    if(k.eq.int(sqrt(float(k)))**2) goto 1
      write(6,*) "The number is ",n
      End

# -*- coding: cp936 -*-
#Å·À­¹¤³Ì 46 Ìâ
#ÈκÎÒ»¸öÆæºÏÊý¶¼ÄÜд³ÉÒ»¸öËØÊýÓëÒ»¸öƽ·½ÊýµÄ¶þ±¶µÄºÍ,Ñ°ÕÒÆÆÀý
#n=prime+2*m**2
from math import sqrt
def isprime(p):    #ÑéÖ¤ÊÇ·ñËØÊý£¬ËØÊý·µ»Ø±¾Éí£¬ºÏÊý·µ»ØFalse
    k=1
    for i in xrange(2,int(sqrt(p))+1):
        if p%i==0:
            k=0
            return False
            break
    if k:
        return p
n=35
while True:
    killer=1                   #ÉèÖòÂÏëµÄÅжϲÎÊý
    if not isprime(n):         #ÑéÖ¤ÊÇ·ñËØÊý£¬ËØÊýÔònµÝÔö¼ÌÐøÏÂһѭ»·£¬ºÏÊý½øÐÐÏÂÒ»²½ÑéÖ¤
        for i in xrange(3,n-1):#×îСµÄËØÊýӦΪ3£¬ÈôΪ2£¬ÔòÎÞ·¨ÐγÉÆæºÏÊý
            if isprime(i) and (sqrt((n-i)/2))%1==0:#¸¡µãÊýÈ¡Ó࣬ºÇºÇ£¬»¹ÊÇpython·½±ã
                killer=0   #·ûºÏ²ÂÏë
                break
    else:
        n+=2
        continue
    if killer:                 #ÑéÖ¤Íê±Ï£¬²»·ûºÏ²ÂÏ룬¼´Îª½á¹û
        print('the number is:%d')%n
        break
    else:
        n+=2

from math import sqrt
n=10000
primes=[2,3]
oddcomp=[]
for i in range(5,n,2):
    isprime=True
    for j in primes:
        if j*j>=i: break
        if i%j==0:
            isprime=False
            break
    if isprime:
        primes.append(i)
    else:
        oddcomp.append(i)
   
res=[p+2*j*j for p in primes for j in range(1,int(sqrt(n))+1)]
print set(oddcomp)-(set(res)|set(primes))

set([5777, 5993])

8Â¥: Originally posted by sudo at 2011-09-05 15:10:50:
ÎÒÓÖ¿´µ½ÁËÒ»¸öͦÀ§ÄѵÄÊýÂÛËã·¨ÎÊÌ⣺

¡°ÈçºÎ¿ìËÙÅжÏÒ»¸öÕûÊýÊÇ·ñΪÍêȫƽ·½Êý¡±

ÕâÓ¦¸ÃÊDZ¾Ìâ×»ªµÄµØ·½...