Skip to content

Instantly share code, notes, and snippets.

@lewtds
Created December 8, 2012 17:34
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save lewtds/4241119 to your computer and use it in GitHub Desktop.
Save lewtds/4241119 to your computer and use it in GitHub Desktop.
#!/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
Copy link

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
Copy link

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
Copy link
Author

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
Copy link

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