01/10/2018, 10:48
Ý tưởng kiểm chứng giả thuyết goldbach
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
Bài liên quan
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)