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

#1

mọi người giúp mình bài này với ạ.mình nghĩ nãy giờ rồi mà ko ra :frowning:
(Tên file bài làm GOLDBACH.PAS) Một giả thuyết chưa được chứng minh trong toán học của Goldbach: Mọi số chẵn lớn hơn 2 đều có thể phân tích thành tổng của hai số nguyên tố: Chẳng hạn: 4 = 2 + 2; 6 = 3 + 3; 10 = 3 + 7. Hãy kiểm chứng giả thuyết này: Nhận vào số chẵn 𝑛, tìm hai số nguyên tố 𝑎, 𝑏 thỏa mãn 𝑎 + 𝑏 = 𝑛. Nếu có nhiều cặp số nguyên tố có tổng bằng 𝑛, hãy chỉ ra cặp (𝑎, 𝑏) mà: 𝑎 ≤ 𝑏 và 𝑎 lớn nhất có thể
Dữ liệu: vào từ file GOLDBACH.INP  Một số nguyên dương 𝑛 ≤ 10^9 .
Kết quả: ghi ra file GOLDBACH.OUT  Hai số nguyên tố 𝑎, 𝑏 tìm được cách nhau bởi dấu cách
GOLDBACH.INP 10
GOLDBACH.OUT 5 5

#2

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.

1 Like
#3

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

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

2 Likes
#4

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

#5

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

#6

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

#7

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

#8

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).

1 Like
#9

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ế

#10

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)

1 Like
#11

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.

1 Like
#12

Đầ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ả

#13

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

2 Likes
#14

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

cả phần này nữa

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?