[交流] Euler 工程 第四十一题 已有1人参与

# Project Euler Problem 41
#
#
# Gen Primes

from math import sqrt
from itertools import permutations

def isPrime(n):
    for x in xrange(2, int(sqrt(n))):
        if n % x == 0:
            return False
    return True

num = [9, 8, 7, 6, 5, 4, 3, 2, 1]

l = 9
left = 0
while l > 1:
    for x in permutations(num[left:], l):
        n = int("%d"*l % x)
        if isPrime(n):
            print "It is", n
            l = 1
            break
    l -= 1
    left += 1

Program euler41
    Implicit None
    Integer, Parameter :: N = 7
    Integer, Dimension(N) :: Digits
    Integer :: I, R, X

    ! Digits
    Digits = (/(I, I=N,1,-1)/)

    !$OMP PARALLEL SHARED(Digits) Private(R,I,X)
    !$OMP DO
    Do R = 9, 1, -1
        Do I = 1, Arrangement(N, R)
            X = Permutations(R, I)
            If(IsPrime(X)) Then
                Print *, X
            EndIf
        EndDo
    EndDo
    !$OMP END DO
    !$OMP END PARALLEL

Contains

    Function Arrangement(N, M) Result(R)
        Implicit None
        Integer, intent(in) :: N, M
        Integer :: R
        Integer :: I
        R = 1
        Do I = (N-M+1), N
            R = R * I
        End DO
    EndFunction

    Function IsPrime(N) Result(R)
        Implicit None
        Integer :: N, I
        Logical :: R
        R = .True.
        !$OMP PARALLEL SHARED(N, R) PRIVATE(I)
        !$OMP DO
        DO I = 2, Floor(Sqrt(N*1.0))
            If(Mod(N, I) == 0) Then
                R = .False.
            EndIf
        EndDo
        !$OMP END DO
        !$OMP END PARALLEL
        Return
    EndFunction

    Function Permutations(R, nth) Result(V)
        Implicit None
        Integer, Dimension(N) :: Indices
        Integer, Intent(In) :: R, nth
        Integer :: V
        Integer :: M
        Integer :: Factorial
        Integer :: I, J, K

        Indices = 1
        M = nth - 1
        V = 0
        Factorial = Arrangement(N-1, N-1)

        Do I = 1, R
            J = M / Factorial + 1
            M = Mod(M, Factorial)
            If(N.ne.I) Factorial = Factorial / (N-I)

            ! Find the index
            K = 1
            Do
                If(Indices(K) > 0) J = J - 1
                If(J .eq. 0) Exit
                K = K + 1
            End Do
            Indices(K) = 0

            ! Gen the Number
            V = V*10 + Digits(K)
        EndDo
    EndFunction
End Program euler41

Originally posted by holmescn at 2011-07-13 09:24:04:
Python偷懒版:
# Project Euler Problem 41
#
#
# Gen Primes

from math import sqrt
from itertools import permutations

def isPrime(n):
    for x in xrange(2, int(sqrt(n))):

function result = euler41()
tic;
n = 7; % sum(1:9) mod 3 == 0, sum(1:8) mod 3 == 0
numlist = sort(str2num(perms('1':num2str(n))),'descend'); % get descend sort
result = isprime(numlist);
result = numlist(result==1); % find all primes
result = result(1); % find the biggest
toc;
end

% Elapsed time is 0.284507 seconds.
% ans =
%      7652413