30/09/2018, 16:17
A problem on codefights.com
Description:
For positive integers N and K return true if N can be represented as a sum of K prime numbers (not necessarily distinct) and false otherwise.
Input 1 : integer n
Input 2 : integer k
Output : boolean
bool primeSum(int n, int k) {
//need an idea!!!
}
Làm sao để kiểm tra số n có thể phân tích thành tổng của k số nguyên tố nhỉ?
Bài liên quan
Đây là 1 vấn đề khá hay. Mình xin đưa ra ý kiến sau:
Ta có 1 công cụ là giả thuyết GoldBach:" Mọi số chẵn>=4 đều có thể phân tích thành tổng 2 số nguyên tố".
Mình không biết chứng minh dc hay chưa( hình như là chưa). Nhưng trong giới hán số int thì giả thuyết này có lẽ là đúng.
Ta sẽ đưa các bài toán khác về bài toán này:
Nếu n lẽ. Thì phải là tổng của 1 chẵn(tất nhiên là số 2), và 1 số lẻ. Bạn chỉ cần kiểm tra số lẻ này là SNT hay không.
Nếu n chẵn: m=k-2,q=n-2m. Áp dụng giả thuyết với q.
(Ở đây n=k-2 snt la 2 +1 số chẵn q. kiểm tra
q với dk>=4 là dc)
Nếu n lẽ: m=k-3, q=n-m2-3. lại áp dụng giả thuyết trong th này.
(Ở đây n=k-3 snt là 2+3 +1 số chẵn q. Kiểm tra q>=4 để kết luận)