01/10/2018, 13:39
Sàng nguyên tố Eratosthenes chạy rất lâu
Cho em hỏi là theo như lí thuyết sàng nguyên tố Eratosthenes thì em code được như thế này . Code chạy nhanh hơn thuật toán kiểm tra từng số , nhưng mà với số lớn cỡ 2000000 thì rất lâu. Mấy anh có thể giúp em tối ưu hơn
# em là sv năm nhất , nhà trường dạy python3
n=int(input())
a=[2]
for i in range(3, n, 2):
a.append(i)
for m in a:
for n in a:
if n % m ==0 and n!=m:
a.remove(n)
print(a)
Bài liên quan
Đơn giản là vì đây không phải sàng Eratosthenes.
theo như wikipedia là :
Bước 1: Tạo 1 danh sách các số tự nhiên liên tiếp từ 2 đến n: (2, 3, 4,…, n).
Bước 2: Giả sử tất cả các số trong danh sách đều là số nguyên tố. Trong đó, p = 2 là số nguyên tố đầu tiên.
Bước 3: Tất cả các bội số của p: 2p, 3p, 4p,… sẽ bị đánh dấu vì không phải là số nguyên tố.
Bước 4: Tìm các số còn lại trong danh sách mà chưa bị đánh dấu và phải lớn hơn p. Nếu không còn số nào, dừng tìm kiếm. Ngược lại, gán cho p giá trị bằng số nguyên tố tiếp theo và quay lại bước 3.
Em nghĩ em code đúng như trên rồi mà
Thực chất bạn đang thực hiện việc chia thử n số. Mặt khác đã gọi là sàng thì không thể sử dụng các lệnh kiểu for_each.
Ta biết rằng:
viết như vậy chậm là đúng.
Mình thấy cái này nó không giống sàng eratosthenes lắm… Hôm bữa mình có làm thử một cái theo chuẩn wiki : https://vicoder.net/thuat-toan-sang-eratosthene-de-loc-nguyen-bang-c.html
đúng nhưng mà chậm
lý do:
m
chạy tớin
, trong khi đúng ram
chỉ cần chạy tới căn(n) là đủa.remove(n)
: 1 lần bỏ 1 số n ra khỏi mảnga
phải đôn các số phía sau n lên trước 1 vị trí, hay có thể hiểu đây là 1 vòng for nữa. Vd: 2 3 4 5 6 7 bỏ 4 ra thì phải dồn 5 6 7 lên trước thành 2 3 5 6 7. Nếu phía sau có 2 triệu số thì đôn lên 2 triệu lần…Không đúng vì ban đầu thớt định code sàng cơ.
hiểu đúng thuật toán mà, chậm ở chỗ
a.remove(n)
tốn O(n) thôi, bằng cách nào giảm nó còn O(1) là lẹthêm chỗ m chạy hết từ 2 tới 2 triệu nữa, chỉ cần chạy tới căn(2 triệu) là đủ rồi
đúng rồi, còn thiếu 1 bước nữa là n phải nhảy
m
bước 1 lần chứ ko phải từng bước 1.ko có cách nào làm mảng số nguyên được rồi =)
Thì đó, phân tích ra chẳng khác gì cách chia thử, có điều là bổ ngang thay vì bổ dọc thôi.
Sàng không bao giờ có for_each trong core loop, dẫu có for_each thì cũng chỉ để ghi output.
Rất tiếc, đây vẫn không phải sàng Eratosthenes. http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf
vậy để trả lời cho chủ thớt luôn:
bước 3 ko đúng vì
n
phải nhảy p lần, trong khifor n in a
nhảy từng bước một và bị buộc phải xét xem n có chia hết cho m hay ko, trong khi nhảy 2p, 3p, 4p, v.v… ko cần xét xem n có chia hết cho p hay ko vì n đã là bội của p. Ngoài ra “đánh dấu” loại phải gọn nhẹ, ko có dồn mảng. Ngoài ra nữa ta chỉ xét các bội số từ p*p, (p+1)*p, v.v… chứ đừng xét từ 2p vì 2,3,…,p-1 đã bị loại rồi.@hungsteve : có xét x có chia hết cho p hay ko thì ko phải rồi.
viết luôn cho chủ thớt, chạy tham khảo thôi
E cảm ơn ạ