Kiểm chứng giả thuyết GOLDBACH

B1: Chọn a là số nguyên tố lớn nhất mà bé hơn n.
B2: Kiểm tra (n-a) xem có phải số nguyên tố không.
B3: Nếu đúng thì b = (n-a). Xuất ra cặp (a, b).
B4: Nếu không thì tìm chọn số nguyên tố nhỏ hơn tiếp theo là a, quay lại B2.

^ a sẽ gần với n/2 hơn là 2 đấy bạn

Bài này sàng không nổi chắc phải dùng RM với 10^8 trở đi.

10

RM??là gì vậy bạn???

Kiểm tra nguyên tố Miller-Rabin thì phải.

Mình nghĩ làm như vậy ko đc.vì phải chạy lặp 5*10^8 lần

B1: Chọn a là số nguyên tố lớn nhất mà bé hơn n.
B2: Kiểm tra (n-a) xem có phải số nguyên tố không.
B3: Nếu đúng thì b = (n-a). Xuất ra cặp (a, b).
B4: Nếu không thì tìm chọn số nguyên tố nhỏ hơn tiếp theo là a, quay lại B2.

Làm như bạn thì tối đa phải chạy lặp 5*10^8 lần đấy

Thực ra có hai hướng làm: một là chỉ dùng RM (+ chia thử), hai là dùng sàng sau đó RM (để ăn test max).

Bạn nói rõ hơn được ko.mình vẫn chưa rõ lắm làm sao sàng đc 1 số to như thế

Sàng nguyên tố đến 10^6 thôi. Nếu muốn kiểm tra số nguyên tố với số N cỡ 10^9 thì chạy kiểm tra tất cả các số nguyên tố trong khoảng từ 2 -> sqrt(N)

Bạn nói rõ hơn được ko.mình vẫn chưa rõ lắm làm sao sàng đc 1 số to như thế

Chọn delta rồi sàng trong đoạn [n/2-delta..n/2]. Do tổng Goldbach có mật độ khá dày (chỉ thua số nguyên tố) nên chọn delta từ 5k trở lên.

Đầu tiên, tìm tất cả các số là số nguyền tố từ 2 đến n / 2.
Tiếp theo, với lần lượt từng số đó thử xem hiệu n và số đó có phải là số nguyên tố không
Nếu đúng -> kết quả

n <= 10^9… mình từng sàng từ đầu rồi, mất thời gian lắm

[n/2-delta…n/2]

mình vẩn chưa hiểu khoảng này là khoảng nào.bạn giả thích thêm chút đi

Do tổng Goldbach có mật độ khá dày (chỉ thua số nguyên tố) nên chọn delta từ 5k trở lên.

cả phần này nữa