Ý tưởng kiểm chứng giả thuyết goldbach

[mua_ta (nắng)]

mọi người cho mình hỏi ý tưởng bài này với.Lần trước mình hỏi nhưng chưa nhận được câu trả lời thích đáng nên muốn hỏi lại :v
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

[rogp10]

Mình nghĩ lại rồi, có RM thôi khỏi sieve mất công đừng quên chia thử thôi.

===================================

RM cũng dựa trên đl Fermat nhỏ nhưng giải quyết được những hạn chế của test Fermat (Carmichael numbers). Với n là số ta đang kiểm tra, ta đã biết test Fermat là ntn:

b^(n-1) =? 1 (mod n) với mỗi b

Ta có 1 tiêu chuẩn khác: với p nguyên tố, b^2 = 1 (mod p) <=> b = +/-1 (mod p) với mọi b.

Tới đây bạn có thể viết code, nhưng bạn sẽ tốn khoảng 72 - 120 phép nhân - mod uint64 cho một phép thử RM. Mình cũng ko chắc 1 phép mod uint64 bằng mấy phép mod uint32 nhưng không dưới 2.

Một số số Carmichael:

2^140 = 67 (mod 561)
2^276 = 781 (mod 1105)
2^308 = 1886 (mod 2465)
2^85115 = 140232 (mod 340561)