Sàng nguyên tố Eratosthenes chạy rất lâu

Đơ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:

• Tổng các nghịch đảo có bậc logn (Eratosthenes)
• Trung bình ước nhỏ nhất có bậc sqrtn/logn (chia thử)
  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ớ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…

đúng nhưng mà chậm

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

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ẹ

1. Đã là sàng Eratosthenes từ đầu tới đuôi thì không cần phép chia làm gì.
2. Cho dù remove là O(1) đi nữa thì câu hỏi là: bao nhiêu phép chia được thực hiện? Có phải là n*sqrt(n) không?

đú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 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.

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.

@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

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 ạ