Hướng dẫn dùng python isprime 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 <= r:
    print('\t',f)
    if n % f == 0: return False
    if n % (f+2) == 0: return False
    f += 6
  return True    

Vì tất cả các số nguyên tố> 3 đều có dạng 6n ± 1, một khi chúng ta loại bỏ nó nlà:

1. không phải 2 hoặc 3 (là số nguyên tố) và
2. thậm chí không (với n%2) và
3. 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 đề:

1. 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;
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<2: return False
    for i in range(3, int(n**0.5)+1, 2):   # only odd numbers
        if n%i==0:
            return False    

    return True

OK - điều đó tăng tốc khoảng 30% (tôi đã đánh giá nó ...)

Thuật toán tôi đã sử dụng is_primevẫn nhanh hơn khoảng 2 lần, vì chỉ mỗi số nguyên thứ 6 là lặp lại vòng lặp. (Một lần nữa, tôi đã chuẩn hóa nó.)

Lưu ý: x ** 0,5 là căn bậc hai:

>>> 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 <= n:
         if n % k == 0:
             return False
         k += 2
    return True

13 hữu ích 5 bình luận chia sẻ

answer

13

Câu hỏi đã được hỏi một chút trước đây, nhưng tôi có một giải pháp ngắn hơn cho bạn

def isNotPrime(Number):
    return 2 not in [Number,2**Number%Number]

Phép toán hầu hết sẽ trả về 2 nếu số là số nguyên tố, thay vì 2. Nhưng nếu 2 là số đã cho, nó sẽ được thêm vào danh sách mà chúng ta đang xem xét.

Ví dụ:

2^5=32    32%5=2
2^7=128   128%7=2
2^11=2048 2048%11=2

Ví dụ về bộ đếm:

2^341%341=2,  but 341==11*31
2^561%561=2,  but 561==3*11*17
2^645%645=2,  but 645==3*5*43

isNotPrime () trả về giá trị True nếu Number không phải là số nguyên tố.

13 hữu ích 5 bình luận chia sẻ

answer

6

Phương pháp này sẽ chậm hơn phương pháp đệ quy và liệt kê ở đây, nhưng sử dụng định lý Wilson và chỉ là một dòng duy nhất:

from math import factorial

def is_prime(x):
    return factorial(x - 1)  % x == x - 1

6 hữu ích 0 bình luận chia sẻ

answer

4

Tìm căn bậc hai của một số là cho hiệu quả. ví dụ. Nếu tôi đang cố gắng tìm thừa số của 36, ​​số cao nhất có thể nhân với chính nó để tạo thành 36 là 6. 7 * 7 = 49.

do đó mọi thừa số của 36 phải được nhân với 6 hoặc một số nhỏ hơn.

4 hữu ích 0 bình luận chia sẻ

answer

4

def is_prime(x):
    if x < 2:
        return False
    elif x == 2:
        return True  
    for n in range(2, x):
        if x % n ==0:
            return False
    return True

4 hữu ích 2 bình luận chia sẻ

answer

2

Mọi mã bạn viết phải hiệu quả. Đối với một người mới bắt đầu như bạn, cách dễ nhất là kiểm tra tính chia hết của số 'n' từ 2 đến (n-1) . Điều này mất rất nhiều thời gian khi bạn xem xét những con số rất lớn. Phương pháp căn bậc hai giúp chúng tôi tạo mã nhanh hơn bởi số lượng phép so sánh ít hơn. Đọc về sự phức tạp trong Thiết kế và Phân tích Thuật toán.

2 hữu ích 1 bình luận chia sẻ

answer

2

Tôi không biết mình có đến muộn không nhưng tôi sẽ để nó ở đây để giúp ai đó trong tương lai.

Chúng tôi sử dụng căn bậc hai của (n) tức là int (n ** 0,5) để giảm phạm vi số mà chương trình của bạn sẽ buộc phải tính toán.

Ví dụ, chúng ta có thể thực hiện phép chia thử để kiểm tra tính nguyên thủy của 100. Hãy xem xét tất cả các ước của 100:

2, 4, 5, 10, 20, 25, 50 Ở đây ta thấy thừa số lớn nhất là 100/2 = 50. Điều này đúng với mọi n: tất cả các ước đều nhỏ hơn hoặc bằng n / 2. Nếu chúng ta xem xét kỹ hơn các ước số, chúng ta sẽ thấy rằng một số trong số chúng là dư thừa. Nếu chúng ta viết danh sách theo cách khác:

100 = 2 × 50 = 4 × 25 = 5 × 20 = 10 × 10 = 20 × 5 = 25 × 4 = 50 × 2 thì sự dư thừa trở nên hiển nhiên. Khi chúng ta đạt đến 10, tức là √100, các ước số chỉ cần lật lại và lặp lại. Do đó, chúng ta có thể loại bỏ thêm ước số thử nghiệm lớn hơn √n.

Lấy một số khác như 16.

Các ước của nó là, 2,4,8

16 = 2 * 8, 4 * 4, 8 * 2.

Bạn có thể lưu ý rằng sau khi đạt đến 4, là căn bậc hai của 16, chúng tôi lặp lại 8 * 2 mà chúng tôi đã thực hiện là 2 * 8. Mô hình này đúng cho tất cả các số.

Do đó, để tránh lặp lại chính mình, chúng tôi kiểm tra tính nguyên thủy lên đến căn bậc hai của một số n.

Vì vậy, chúng tôi chuyển đổi căn bậc hai thành int vì chúng tôi không muốn một phạm vi có số thực.

Đọc bài kiểm tra tính nguyên thủy trên wikipedia để biết thêm thông tin.

2 hữu ích 0 bình luận chia sẻ

answer

2

Đây là phương pháp của tôi:

import math

def isPrime(n):
    'Returns True if n is prime, False if n is not prime. Will not work if n is 0 or 1'

    # Make sure n is a positive integer
    n = abs(int(n))

    # Case 1: the number is 2 (prime)
    if n == 2: return True

    # Case 2: the number is even (not prime)
    if n % 2 == 0: return False

    # Case 3: the number is odd (could be prime or not)

    # Check odd numbers less than the square root for possible factors 
    r = math.sqrt(n)
    x = 3 
    while x <= r:
        if n % x == 0: return False  # A factor was found, so number is not prime
        x += 2 # Increment to the next odd number

    # No factors found, so number is prime  
    return True 

Để trả lời câu hỏi ban đầu, n ** 0,5 bằng với bình phương của n . Bạn có thể ngừng kiểm tra các thừa số sau số này vì một số tổng hợp sẽ luôn có một thừa số nhỏ hơn hoặc bằng căn bậc hai của nó. Điều này nhanh hơn so với việc chỉ kiểm tra tất cả các thừa số từ 2 đến n cho mọi n, bởi vì chúng tôi kiểm tra số lượng ít hơn, điều này giúp tiết kiệm nhiều thời gian hơn khi n lớn lên.

2 hữu ích 0 bình luận chia sẻ

answer

2

def isPrime(num,div=2):
    if(num==div):
        return True
    elif(num % div == 0):
        return False
    else:
        return isPrime(num,div+1)

==============================================
ĐÃ CHỈNH SỬA

def is_prime(num, div = 2):
    if num == div: return True
    elif num % div == 0: return False
    elif num == 1: return False
    else: return is_prime(num, div + 1)

2 hữu ích 2 bình luận chia sẻ

answer

1

isPrime=lambda x: all(x % i != 0 for i in range(int(x**0.5)+1)[2:])

và đây là cách sử dụng nó

isPrime(2) == False
isPrime(5) == True
isPrime(7) == True

Để tìm tất cả các số nguyên tố, bạn có thể sử dụng:

filter(isPrime, range(4000)[2:])[:5]
=> [2, 3, 5, 7, 11]

Lưu ý rằng 5, trong trường hợp này, biểu thị số lượng các số nguyên tố được tìm thấy và 4000 phạm vi tối đa của các số nguyên tố sẽ được tìm kiếm.

1 hữu ích 0 bình luận chia sẻ

answer

1

def is_prime(x):  
    if x < 2:  
        return False  
    for n in range(2, (x) - 1):  
        if x % n == 0:  
            return False  
    return True

1 hữu ích 2 bình luận chia sẻ

answer

1

Đã triển khai mã giả ( https://en.wikipedia.org/wiki/Primality_test ) trong python, hy vọng điều này sẽ giúp ích cho bạn.

# original pseudocode https://en.wikipedia.org/wiki/Primality_test
def isPrime(n):
    # Corner Cases
    if (n<= 1): return False
    elif (n<= 3): return True
    elif (n%2 == 0 or n%3 == 0): return False

    i = 5
    while i*i<=n:
        if (n%i==0 or n%(i+2)==0): return False
        i += 6

    return True;

%timeit isPrime(800)

1 hữu ích 2 bình luận chia sẻ

answer

0

int(n**0.5)là giá trị sàn của sqrt (n) mà bạn nhầm lẫn với lũy thừa 2 của n (n**2). Nếu nlà không đắc địa, phải có hai số 1 < i <= j < nsao cho: i * j = n.

Bây giờ, vì sqrt(n) * sqrt(n) = ngiả sử một trong hai i,jlớn hơn (hoặc bằng) sqrt(n)- có nghĩa là cái kia phải nhỏ hơn (hoặc bằng) sqrt(n).

Vì đó là trường hợp, đủ tốt để lặp lại các số nguyên trong phạm vi [2, sqrt(n)]. Và đó chính xác là những gì mã được đăng đang làm.

Nếu bạn muốn trở thành một smartass thực sự, hãy sử dụng hàm một lớp lót sau:

import re
def is_prime(n):    
    return not re.match(r'^1?$|^(11+?)\1+$',n*'1')

Có thể tìm thấy lời giải thích cho "ma thuật regex" tại đây

0 hữu ích 4 bình luận chia sẻ

answer

0

Đây là npcách của tôi :

def is_prime(x):
    if x < 4:
        return True
    if all([(x > 2), (x % 2 == 0)]):
        return False
    else:
        return np.array([*map(lambda y: ((x % y) == 0).sum(), np.arange(1, x + 1))]).sum() == 2

Đây là hiệu suất:

%timeit is_prime(2)
%timeit is_prime(int(1e3))
%timeit is_prime(5003)

10000 loops, best of 3: 31.1 µs per loop
10000 loops, best of 3: 33 µs per loop
10 loops, best of 3: 74.2 ms per loop

0 hữu ích 1 bình luận chia sẻ

answer

0

def is_prime(n):
    n=abs(n)
    if n<2:    #Numbers less than 2 are not prime numbers
        return "False"
    elif n==2: #2 is a prime number
        return "True"
    else:
        for i in range(2,n): # Highlights range numbers that can't be  a factor of prime number n. 
            if n%i==0:
                return "False" #if any of these numbers are factors of n, n is not a prime number
    return "True" # This is to affirm that n is indeed a prime number after passing all three tests

0 hữu ích 1 bình luận chia sẻ

answer

0

Đó là một bài tập trong codecademy và đó là cách tôi vượt qua nó dưới đây ...

def is_prime(x):  

    # If number(x) is evenly divided by following dividers then number(x) is not prime

    divider = [2, 3, 5, 7]

    # An empty list to be able to check whether number(x) is evenly divided:

    remainder = []

    # exceptions for numbers 1,2,3,5,7:
    if x < 2:
        return False
    if x in divider:
        return True
    else:
        for nums in divider:
            remainder.append(x % nums)
        if 0 in remainder:
            return False
        else:
            return True

0 hữu ích 0 bình luận chia sẻ

answer

0

def is_prime(n):
if (n==2 or n==3): return True
if(n<=1 or n%2==0 or n%3==0 ): return False
for i in range(6,int((n**0.5)) + 2,6):
    if(n%(i-1)==0 or n%(i+1)==0):
        return False
return True

0 hữu ích 1 bình luận chia sẻ

answer

-1

Khá đơn giản!

def prime(x):
  if x == 1:
    return False
  else:
    for a in range(2,x):
      if x % a == 0:
        return False
  return True

-1 hữu ích 0 bình luận chia sẻ

answer

-1

Đây là của tôi

import math

def is_prime(num):

    if num % 2 == 0 and num > 2: 
       return False
    for i in range(3, int(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False
    return True

-1 hữu ích 1 bình luận chia sẻ

answer

-1

def fun(N):#prime test
if N>1 :
    for _ in xrange(5):
        Num=randint(1,N-1)
        if pow(Num,N-1,N)!=1:
            return False
    return True
return False

Đúng nếu số là số nguyên tố, ngược lại là sai

-1 hữu ích 0 bình luận chia sẻ

answer

-1

Số 1 là một trường hợp đặc biệt không được coi là số nguyên tố cũng không phải là hợp số. Để biết thêm thông tin, hãy truy cập: http://mathworld.wolfram.com/PrimeNumber.html

Và, (n ** 0,5) -> Điều này sẽ cho chúng ta " căn bậc hai " của 'n'. Vì nó là "n được nâng lên thành lũy thừa 0,5 hoặc 1/2"

Và TẠI SAO chúng ta làm điều đó, Lấy ví dụ số 400: Chúng ta có thể biểu diễn nó dưới dạng a * b

1*400 = 400
2*200 = 400
4*100 = 400
5*80 = 400
8*50 = 400
10*40 = 400
16*25 = 400
20*20 = 400
25*16 = 400
40*10 = 400
50*8 = 400
80*5 = 400
100*4 = 400
200*2 = 400
400*1 = 400

Căn bậc hai của 400 là 20: và chúng ta có thể thấy rằng chúng ta chỉ cần kiểm tra tính chia hết cho đến 20 bởi vì, khi 'a' đến 20 'b' bắt đầu giảm ... Vì vậy, cuối cùng chúng ta đang kiểm tra tính chia hết với các số nhỏ hơn căn bậc hai.

-1 hữu ích 0 bình luận chia sẻ

answer

-1

Tôi có một giải pháp mới mà tôi nghĩ có thể nhanh hơn bất kỳ Hàm nào được đề cập trong Python

Nó dựa trên ý tưởng rằng: N / D = R với bất kỳ số N tùy ý nào, số nhỏ nhất có thể để chia N (nếu không phải là số nguyên tố) là D = 2 và kết quả tương ứng R là (N / 2) (cao nhất).

Khi D lớn hơn kết quả R nhỏ hơn ví dụ: chia cho D = 3 kết quả R = (N / 3) vì vậy khi chúng ta kiểm tra xem N có chia hết cho D hay không, chúng ta cũng đang kiểm tra xem nó có chia hết cho R không

vì vậy D lớn hơn và R nhỏ hơn cho đến (D == R == căn bậc hai (N))

thì chúng ta chỉ cần kiểm tra các số từ 2 đến sqrt (N) một mẹo khác để tiết kiệm thời gian, chúng ta chỉ cần kiểm tra các số lẻ vì nó là số chia hết cho số chẵn thì nó cũng sẽ chia hết cho 2.

vì vậy dãy sẽ là 3,5,7,9, ......, sqrt (N).

import math
def IsPrime (n): 
    if (n <= 1 or n % 2 == 0):return False
    if n == 2:return True
    for i in range(3,int(math.sqrt(n))+1,2):
        if (n % i) == 0:
            return False
    return True

-1 hữu ích 0 bình luận chia sẻ

answer

-1

( https://www.youtube.com/watch?v=Vxw1b8f_yts&t=3384s ) Avinash Jain

for i in range(2,5003):
    j = 2
    c = 0
    while j < i:
        if i % j == 0:
            c = 1
            j = j + 1
        else:
            j = j + 1
    if c == 0:
        print(str(i) + ' is a prime number')
    else:
        c = 0

-1 hữu ích 0 bình luận chia sẻ

answer

-3

def is_prime(x):  
    if x<2:  
        return False  
    elif x == 2:  
        return True  
    else:  
        for n in range(2, x):  
            if x%n==0:  
                return False  
        return True

-3 hữu ích 0 bình luận chia sẻ

answer

-4

Srsly guys ... Tại sao rất nhiều dòng mã cho một phương pháp đơn giản như thế này? Đây là giải pháp của tôi:

def isPrime(a):
    div = a - 1
    res = True
    while(div > 1):
        if a % div == 0:
            res = False
        div = div - 1
    return res

-4 hữu ích 1 bình luận chia sẻ