Hướng dẫn dùng isprime python python

answer

100

Trong số nhiều bài kiểm tra số nguyên tố trôi nổi trên Internet, hãy xem xét hàm Python sau:

def is_prime[n]:
  if n == 2 or n == 3: return True
  if n < 2 or n%2 == 0: return False
  if n < 9: return True
  if n%3 == 0: return False
  r = int[n**0.5]
  # since all primes > 3 are of the form 6n ± 1
  # start with f=5 [which is prime]
  # and test f, f+2 for being prime
  # then loop by 6. 
  f = 5
  while f  3 đều có dạng 6n ± 1, một khi chúng ta loại bỏ nó nlà:
không phải 2 hoặc 3 [là số nguyên tố] và
thậm chí không [với n%2] và
không chia hết cho 3 [với n%3] thì ta có thể nghiệm cứ thứ 6 n ± 1.
Xét số nguyên tố 5003:
print is_prime[5003]
Bản in:
 5
 11
 17
 23
 29
 35
 41
 47
 53
 59
 65
True
Dòng
có r = int[n**0.5]giá trị 70 [căn bậc hai của 5003 là 70,7318881411 và int[]cắt bớt giá trị này]

  

Hãy xem xét số lẻ tiếp theo [vì tất cả các số chẵn khác 2 không phải là số nguyên tố] của 5005, điều tương tự in ra:
 5
False
Giới hạn là căn bậc hai vì x*y == y*xHàm chỉ phải đi 1 vòng lặp để thấy rằng 5005 chia hết cho 5 và do đó không phải là số nguyên tố. Vì 5 X 1001 == 1001 X 5[và cả hai đều là 5005], chúng ta không cần phải đi đến 1001 trong vòng lặp để biết những gì chúng ta biết ở 5!
Bây
giờ, hãy xem xét thuật toán mà bạn có:
def isPrime[n]:
    for i in range[2, int[n**0.5]+1]:
        if n % i == 0:
            return False

    return True
Có hai vấn đề:
Nó không kiểm tra nếu nnhỏ hơn 2 và không có số nguyên tố nào nhỏ hơn 2;
Nó kiểm tra mọi số từ 2 đến n ** 0,5 bao gồm tất cả các số chẵn và tất cả các số lẻ. Vì mọi số lớn hơn 2 chia hết cho 2 đều không phải là số nguyên tố, nên chúng ta có thể tăng tốc một chút bằng cách chỉ thử nghiệm các số lẻ lớn hơn 2.
Vì thế:
def isPrime2[n]:
    if n==2 or n==3: return True
    if n%2==0 or n>> import math
>>> math.sqrt[100]==100**0.5
True
Lưu ý 2: Kiểm tra tính nguyên sơ là một vấn đề thú vị trong khoa học máy tính.
  100 hữu ích    5 bình luận    chia sẻ 
answer 
21
Với n**.5, bạn không bình phương n, nhưng lấy căn bậc hai.
Hãy xem xét các số 20; các thừa số nguyên là 1, 2, 4, 5, 10 và 20. Khi bạn chia 20 cho 2 và được 10, bạn biết rằng nó cũng chia hết cho 10 mà không cần phải kiểm tra. Khi bạn
chia cho 4 và được 5, bạn biết nó chia hết cho cả 4 và 5 mà không cần phải kiểm tra lại cho 5.
Sau khi đạt đến nửa điểm này trong các yếu tố, bạn sẽ không còn số để kiểm tra xem bạn chưa nhận ra yếu tố nào trước đó. Do đó, bạn chỉ cần đi một nửa để xem một cái gì đó có phải là số nguyên tố hay không, và điểm nửa chừng này có thể được tìm thấy bằng cách lấy căn bậc hai của số đó.
Ngoài ra, lý do 1 không phải là số nguyên tố là vì số nguyên tố được định nghĩa là có 2 thừa số, 1 và
chính nó. tức là 2 là 1 * 2, 3 là 1 * 3, 5 là 1 * 5. Nhưng 1 [1 * 1] chỉ có 1 yếu tố, chính nó. Do đó, nó không đáp ứng định nghĩa này.
  21 hữu ích    1 bình luận    chia sẻ 
answer 
13
Không có hoạt động dấu chấm động nào được thực hiện bên dưới. Điều này nhanh hơn và sẽ chịu được các đối số cao hơn. Lý do bạn chỉ phải đi đến căn bậc hai là nếu một số có thừa số lớn hơn căn bậc
hai của nó, nó cũng có thừa số nhỏ hơn nó.
def is_prime[n]:
    """"pre-condition: n is a nonnegative integer
    post-condition: return True if n is prime and False otherwise."""
    if n < 2: 
         return False;
    if n % 2 == 0:             
         return n == 2  # return False
    k = 3
    while k*k