Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#!/usr/bin/env python3
import itertools # Thư viện chuẩn của Python để xử lý các vấn đề lặp, tổ hợp,
# chỉnh hợp,...
def is_prime(num):
if num < 2:
return False
if num == 2:
return True
if not num % 2:
return False
i = 3
while i ** 2 <= num:
if not num % i:
return False
i += 2
return True
def main():
# 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 is_prime(num):
print(num)
break
if __name__ == '__main__':
main()
@thuandt

This comment has been minimized.

Copy link

@thuandt thuandt commented Dec 9, 2012

Anh fork và dùng thuật toán isPrime khác.
Thời gian chạy giữa is_prime và isPrime
is_prime


Answer :  987654103
Time   :  0.0100979804993

isPrime


Answer :  987654103
Time   :  0.00563597679138
@thuandt

This comment has been minimized.

Copy link

@thuandt thuandt commented Dec 9, 2012

Some useful facts:
1 is not a prime.
All primes except 2 are odd.
All primes greater than 3 can be written in the form  6k+/-1.
Any number n can have only one primefactor greater than n .
The consequence for primality testing of a number n is: if we cannot find a number f less than 
or equal  n that divides n then n is prime: the only primefactor of n is n itself
@lewtds

This comment has been minimized.

Copy link
Owner Author

@lewtds lewtds commented Dec 10, 2012

Em không giỏi thuật toán lắm, nhất là cái số nguyên tố thì lại càng tệ :">
Mà em xem qua code của anh rồi. Đang Python 3 đẹp đẽ, chả cần "-*- coding" tự dưng nhảy về Python 2 trông buồn quá :v

@thuandt

This comment has been minimized.

Copy link

@thuandt thuandt commented Dec 12, 2012

Cái header đấy anh để mặc định cho hết đống python code của anh mà :)
Giờ vẫn xài python2 nhiều, Ubuntu/Debian/CentOS vẫn python2 mà :p

Mấy cái thuật toán Prime này là đợt anh làm Project Euler nên mới biết.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment