[交流] Project Euler 46 欧拉工程 46 题 已有4人参与

8楼: Originally posted by sudo at 2011-09-05 15:10:50:
我又看到了一个挺困难的数论算法问题：

“如何快速判断一个整数是否为完全平方数”

这应该是本题最精华的地方...

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