[交流] Project Euler 49 欧拉工程 49 题

# -*- coding: cp936 -*-
#Project Euler 49 欧拉工程 49 题
#等差3330数列
#(1)每一项都是四位数的素数
#(2)任一项都可以通过其他项再排列得到
#由4位素数组成的三个数
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
for x in xrange(1001,3338):   #9999-6660=3339，x为三个数中最小的，不大于此
    if isprime(x) and isprime(x+3330) and isprime(x+6660) and set(str(x))==set(str(x+3330))==set(str(x+6660)):
        print x,x+3330,x+6660

1487 4817 8147
2969 6299 9629

['148748178147', '296962999629']

#!/usr/bin/env python

def generatePrimes(n):#generate all prime numbers less than a given integer n, just take 0.6 seconds for the case n equals one million
    isprimes=[True]*n
    for i in range(2,n):
        if isprimes[i]:
            for j in range(2*i,n,i):
                isprimes[j] = False
    primes=[i for i in range(3,n,2) if isprimes[i]]
    primes.insert(0,2)
    return primes


def euler49():
    p1=generatePrimes(10000)
    p2=[i for i in p1 if i>1000]   
   
    res=[]
    for i in p2:
        for j in p2:
            if j>i and set(str(i))==set(str(j)):
                k=2*j-i
                if set(str(k))==set(str(i)) and k in p2:
                    res.append(''.join([str(i),str(j),str(k)]))

    return res


if __name__ == "__main__":
    print euler49()

3楼: Originally posted by wangww2011 at 2011-09-09 12:05:16:
结果

CODE:

['148748178147', '296962999629']

代码
[code]
#!/usr/bin/env python

def generatePrimes(n):#generate all prime numbers less than a given integer n, just take 0.6 seconds  ...

3楼: Originally posted by wangww2011 at 2011-09-09 12:05:16:
结果

CODE:

['148748178147', '296962999629']

代码
[code]
#!/usr/bin/env python

def generatePrimes(n):#generate all prime numbers less than a given integer n, just take 0.6 seconds  ...

% ans =
% 296962999629
function result = euler49()
tic;
result = '';
for i=1488:9999  
    % get current string
    a = num2str(i);
   
    % except 1487, 4817, 8147
    if strcmp(unique(a),'1478')
        continue;
    end
   
    % all permutation of current number's digits
    b = perms(a);
   
    % only check primes
    b(~isprime(str2num(b)),:) = [];
   
    % less than 3 left, jumpt over
    if size(b,1)<3
        continue;
    end
   
    % sort ascend
    b = sortrows(b);
   
    % 2nd-1st==3rd-2nd, so 1st+3rd=2*2nd
    % b(j), 1st
    for j=1:size(b,1)
        % b(k), 3rd
        for k=size(b,1):-1:j+1
            % mid, 2nd
            mid = (str2double(b(j,:))+str2double(b(k,:)))/2;
            
            % b(j,:)!=b(k,:) and 2nd is a row of b
            if ~strcmp(b(j,:),b(k,:)) && ismember(num2str(mid),b,'rows')
                result = [b(j,:),num2str(mid),b(k,:)];
                break
            end
        end
        
        % find, break
        if ~isempty(result)
            break;
        end
    end
   
    % find, break
    if ~isempty(result)
        break;
    end
end % end of i
toc;
end