Bạn chỉ cần kiểm tra các giá trị nguyên tố trong phạm vi của các ước số có thể - ví dụ, nếu một giá trị không chia hết cho 2, nó sẽ không chia hết cho bất kỳ bội số nào của 2 giá trị đó; tương tự như vậy đối với mọi số nguyên tố và số nguyên tố khác. Vì vậy, trong ví dụ của bạn, bạn có thể kiểm tra 2, 3, 5 - bạn không cần phải kiểm tra 4, bởi vì mọi thứ chia hết cho 4 phải chia hết cho 2. Do đó, cách tiếp cận nhanh hơn sẽ tính toán số nguyên tố trong bất kỳ phạm vi nào bạn quan tâm, và sau đó chỉ đơn giản là tính toán các giá trị mà chúng phân chia.
Tăng tốc khác là thêm mỗi giá trị trong phạm vi bạn quan tâm đến một số set: khi bạn thấy rằng nó có thể chia hết cho một số trong phạm vi của bạn, hãy xóa số đó khỏi tập hợp. Sau đó, bạn chỉ nên thử nghiệm các số còn lại trong tập hợp - điều này sẽ ngăn bạn kiểm tra các số nhiều lần.
Nếu chúng tôi kết hợp hai cách tiếp cận này, chúng ta thấy rằng chúng ta có thể tạo ra một set của tất cả các giá trị (như vậy trong ví dụ này, một bộ với tất cả các giá trị từ 1 đến 10), và chỉ cần loại bỏ các bội số của mỗi số nguyên tố trong dãy thứ hai của bạn từ bộ đó.
Chỉnh sửa: Như Patashu đã chỉ ra, điều này sẽ không hoàn toàn hoạt động nếu phần tử phân chia giá trị đã cho không có trong tập hợp. Để khắc phục điều này, chúng tôi có thể áp dụng thuật toán tương tự như trên: tạo một set với các giá trị [a, b], cho mỗi giá trị trong set, xóa tất cả bội số của nó. Vì vậy, đối với ví dụ được đưa ra dưới đây trong các ý kiến (với [3, 6]), chúng tôi sẽ bắt đầu với 3 và loại bỏ bội số của nó trong tập hợp - như vậy 6. Do đó, các giá trị còn lại chúng ta cần kiểm tra sẽ là [3, 4, 5] đó là những gì chúng ta muốn trong trường hợp này.
Edit2: Đây là một thực sự bị hack lên, không hấp dẫn thi hành mà chưa được tối ưu hóa và có tên biến khủng khiếp:
def find_non_factors():
a = 1
b = 1000000
x = 200
y = 1000
z = [True for p in range(x, y+1)]
for k, i in enumerate(z):
if i:
k += x
n = 2
while n * k < y + 1:
z[(n*k) - x] = False
n += 1
k = {p for p in range(a, b+1)}
for p, v in enumerate(z):
if v:
t = p + x
n = 1
while n * t < (b + 1):
if (n * t) in k:
k.remove(n * t)
n += 1
return k
Hãy thử thực hiện ban đầu của bạn với những con số. Mất> 1 phút trên máy tính của tôi. Quá trình triển khai này mất dưới 2 giây.
Bạn có tối ưu hóa lớn (b-a), lớn b, lớn (y-x), lớn hoặc gọi nhiều lần với số lượng nhỏ? Tôi nghi ngờ câu trả lời sẽ khác nhau tùy thuộc vào những câu hỏi – Patashu
Đó là một phần của vấn đề: a, b, x, y, tăng dần dần – JohnWO
Bạn không muốn viết 1e100 thay vì "1, e + 100"? Nếu đây là trường hợp, sau đó sẽ rất khó để tìm thấy một phương pháp rất nhanh, như tập hợp các số không phù hợp trong bộ nhớ, hoặc thậm chí là một ổ đĩa cứng (cho đến nay). Nếu số lượng là hợp lý (nói khoảng 1e8, để chúng phù hợp với bộ nhớ), thì một cách tiếp cận nhanh có thể thu được bằng cách trao đổi bộ nhớ cho tốc độ. – EOL