Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
#!/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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment