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)Đơ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:
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ới n, trong khi đúng ra m 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ảng a 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 khi for 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.
@hungaya : 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
from math import sqrt
N = int(input())
sqrtN = int(sqrt(N))
sieve = [True] * (N+1) # sàng nguyên tố: nếu sieve[x] == True thì x là số nguyên tố
sieve[0] = sieve[1] = False # ko cần cũng ko sao, viết luôn cho nó đúng nghĩa
for p in range(2, sqrtN+1): # p chỉ chạy tới căn(N)
if not sieve[p]: continue # chỉ tiếp tục bước 3 nếu p là số nguyên tố
for n in range(p*p, N+1, p): # n chạy từ p*p tới N, nhảy p lần nên n luôn là bội của p, ko cần xét n % p == 0
sieve[n] = False # đánh dấu ko phải là số nguyên tố: chỉ tốn O(1)
for p in range(2, N+1):
if sieve[p]:
print(p, end=' ')
E cảm ơn ạ 
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?