Số nguyên tố ngẫu nhiên trong python

Question

Tôi hiện có ↓ được đặt làm chức năng randprime(p,q). Có cách nào để ngưng tụ điều này, thông qua một cái gì đó như một số điện thoại genexp hoặc listcomp? Đây là chức năng của tôi:

n = randint(p, q) 
while not isPrime(n): 
    n = randint(p, q) 

Answer 1

Tốt hơn là chỉ tạo danh sách số nguyên tố, sau đó chọn từ dòng đó. Như vậy, với mã của bạn, cơ hội mỏng sẽ đạt đến vòng lặp vô hạn, nếu không có số nguyên tố trong khoảng thời gian hoặc nếu randint luôn chọn một số nguyên tố thì vòng lặp while sẽ không bao giờ kết thúc.

Vì vậy, đây có lẽ là ngắn hơn và ít rắc rối:

import random 
primes = [i for i in range(p,q) if isPrime(i)] 
n = random.choice(primes) 

Một thuận lợi khác của việc này là không có cơ hội của bế tắc nếu không có số nguyên tố trong khoảng thời gian. Như đã trình bày điều này có thể chậm tùy thuộc vào phạm vi, vì vậy nó sẽ nhanh hơn nếu bạn lưu trữ các số nguyên tố trước thời hạn:

# initialising primes 
minPrime = 0 
maxPrime = 1000 
cached_primes = [i for i in range(minPrime,maxPrime) if isPrime(i)] 

#elsewhere in the code 
import random 
n = random.choice([i for i in cached_primes if p<i<q]) 

Một lần nữa, tối ưu hoá hơn nữa là có thể, nhưng là phụ thuộc rất nhiều vào mã thực tế của bạn .. và bạn biết họ nói gì về sự tối ưu hóa sớm.

Answer 2

next(i for i in itertools.imap(lambda x: random.randint(p,q)|1,itertools.count()) if isPrime(i)) 

Điều này bắt đầu bằng itertools.count() - điều này mang lại một tập hợp vô hạn.

Mỗi số được ánh xạ tới một số ngẫu nhiên mới trong phạm vi, bởi itertools.imap(). imap giống như bản đồ, nhưng trả về một trình lặp, thay vì một danh sách - chúng ta không muốn tạo ra một danh sách các số ngẫu nhiên vô hạn!

Sau đó, tìm thấy số phù hợp đầu tiên và trả về.

Hoạt động hiệu quả, ngay cả khi p và q cách nhau rất xa - ví dụ: 1 và 10 ** 30, tạo danh sách đầy đủ sẽ không hoạt động!

Nhân tiện, điều này không hiệu quả hơn mã của bạn ở trên và khó hiểu hơn rất nhiều - vui lòng xem xét lập trình viên tiếp theo để đọc mã của bạn và chỉ cần làm như bạn đã làm ở trên. Lập trình viên đó có thể là bạn trong sáu tháng, khi bạn quên mã này được cho là phải làm gì!

P.S - trong thực tế, bạn có thể muốn thay thế count() bằng xrange (KHÔNG phạm vi!), Ví dụ: xrange((p-q)**1.5+20) không được nhiều hơn số lần thử (cân bằng giữa các thử nghiệm giới hạn cho phạm vi nhỏ và phạm vi rộng và không có hơn 1/2% cơ hội thất bại nếu thành công), nếu không, như được đề xuất trong một bài đăng khác, bạn có thể lặp lại mãi mãi.

PPS - cải thiện: thay thế random.randint(p,q) với random.randint(p,q)|1 - điều này làm cho mã gấp đôi hiệu quả, nhưng loại trừ khả năng rằng kết quả sẽ là 2.

Answer 3

Vì vậy, nó sẽ là tuyệt vời nếu bạn có thể sử dụng một iterator để cung cấp cho các số nguyên từ p đến q theo thứ tự ngẫu nhiên (không thay thế). Tôi đã không thể tìm ra cách để làm điều đó. Sau đây sẽ cung cấp cho số nguyên ngẫu nhiên trong phạm vi đó và sẽ bỏ qua bất cứ điều gì mà nó đã được thử nghiệm rồi.

import random 
fail = False 
tested = set([]) 
n = random.randint(p,q) 
while not isPrime(n): 
    tested.add(n) 
    if len(tested) == p-q+1: 
     fail = True 
     break 
    while n in s: 
     n = random.randint(p,q) 

if fail: 
    print 'I failed' 
else: 
    print n, ' is prime' 

Lợi thế lớn của điều này là nếu nói phạm vi bạn đang kiểm tra chỉ là (14,15), mã của bạn sẽ chạy vĩnh viễn.Mã này được đảm bảo để tạo ra một câu trả lời nếu một nguyên tố như vậy tồn tại, và cho bạn biết không có một nếu như một nguyên tố không tồn tại. Bạn rõ ràng có thể làm cho nó nhỏ gọn hơn, nhưng tôi đang cố gắng thể hiện logic.