A problem on codefights.com

[minh_vu_03]

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ỉ?

[Gio (Gió)]

Đâ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:

• k=1. Bạn chỉ cần viết hàm kiểm tra số nguyên tố là xong.
• k=2. Nếu n chẵn và thoã mãn đk trên thì reurn true; else false.
  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.
• k>=3. Tuỳ theo n chẵn hay lẻ:
  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)