Tìm số nguyên tố lớn nhất có 9 chữ số và các chữ số khác nhau từng đôi một

unique_digit_prime.py

#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
#      Filename:  prime.py
#
#   Description:  Tìm số nguyên tố lớn nhất có 9 chữ số khác nhau
#
#       Created:  12/09/2012 06:32:33 AM
# Last Modified:  12/09/2012 06:40:49 AM


import time
import itertools


def isPrime(n):
    if (n < 2):
        return False
    elif (n < 4):  # 2 and 3 is prime
        return True
    elif (n % 2 == 0):
        return False
    elif (n < 9):  # we have already excluded 4,6 and 8.
        return True
    elif (n % 3 == 0):
        return False
    else:
        i = 5
        # sqrt(n) rounded to the greatest integer r so that r*r<=n
        while (i * i <= n):
            if (n % i == 0):
                return False
            if (n % (i + 2) == 0):
                return False
            i += 6
        return True


def main():  # main
    start = time.time()

    result = 0

    # Lặp qua tất cả các chỉnh hợp chập 9 của cái cục kia. Chú ý là thứ tự
    # chỉnh hợp của hàm permutations đưa ra đã được sort sẵn
    for i in itertools.permutations(
            ['9', '8', '7', '6', '5', '4', '3', '2', '1', '0'], 9):
        if i[-1] in ['0', '2', '4', '5', '6', '8']:  # ký tự cuối cùng
            continue
        num = int(''.join(i))  # Nối string thành int

        if isPrime(num):
            result = num
            break

    # Print Answer and Time Execute
    print "Answer : ", result
    print "Time   : ", str(time.time() - start)
    return 0

if __name__ == '__main__':
    print __doc__
    main()