Hackerrank--Prime Sum

The problem is quite simple. You're given a number N and a positive integer K. Tell if N can be represented as a sum of K prime numbers (not necessarily distinct).

Input Format
The first line contains a single integer T, denoting the number of test cases.
Each of the next T lines contains two positive integers, N & K, separated by a single space.

Output Format
For every test case, output "Yes" or "No" (without quotes).

Constraints
1 <= T <= 5000
1 <= N <= 1012
1 <= K <= 1012

Sample Input
2
10 2
1 6
Sample Output
Yes
No
Explanation

In the first case, 10 can be written as 5 + 5, and 5 is a prime number. In the second case, 1 cannot be represented as a sum of prime numbers, because there are no prime numbers less than 1.

题意：给两个正整数ｎ和ｋ，问能否将ｎ分解为ｋ个素数的和（可以出现相同的）。

思路：本题涉及的知识点有哥德巴赫猜想（任何大于２的偶数都可以拆分成两个素数的和），

还有Miller-Rabin素数测试，一般使用的素数测试是O(sqrt(n))复杂度的，无法满足大整数的要求。

费马小定理: 如果p是一个素数,且(0<a<p),则

例如,67是一个素数,则2^66 mod 67=1.

利用费马小定理,对于给定的整数n,可以设计一个素数判定算法.通过计算d=2^(n-1) mod n 来判定整数n的素性.当d≠1时,n肯定不是素数;当d=1时,n则很可能是素数,但也存在合数n,使得 .例如,满足此条件的最小合数是n=341.为了提高测试的准确性,我们可以随机地选取整数1<a<n-1,然后用条件来判定整数n的素性.例如对于n=341,取a=3时,有 ,故可判定n不是素数.

费马小定理毕竟只是素数判定的一个必要条件.满足费马小定理条件的整数n未必全是素数.有些合数也满足费马小定理的条件.这些合数被称作Carmichael数,前3个Carmichael数是561,1105,1729. Carmichael数是非常少的.在1~100000000范围内的整数中,只有255个Carmichael数.

利用下面的二次探测定理可以对上面的素数判定算法作进一步改进,以避免将Carmichael数当作素数.

二次探测定理 如果p是一个素数,且0<x<p,则方程x*x≡1(mod p)的解为x=1,p-1.

事实上, x*x≡1(mod p)等价于 x*x-1≡0(mod p).由此可知;

(x-1)(x+1) ≡1(mod p)

故p必须整除x-1或x+1.由p是素数且 0<x<p,推出x=1或x=p-1.

利用二次探测定理,我们可以在利用费马小定理计算 a^(n-1) mod n的过程中增加对于整数n的二次探测.一旦发现违背二次探测条件,即可得出n不是素数的结论.

Accepted Code:

 1 #include <ctime>
 2 #include <iostream>
 3 using namespace std;
 4 
 5 typedef long long LL;
 6 
 7 LL mulMod(LL a, LL b, LL c) {
 8     LL res = 0;
 9     while (b) {
10         if (b&1) if ((res = (res + a)) >= c) res -= c;
11         a = a + a;
12         if (a >= c) a -= c;
13         b >>= 1;
14     }
15     return res;
16 }
17 
18 LL powMod(LL a, LL b, LL c) {
19     LL res = 1;
20     while (b) {
21         if (b&1) res = mulMod(res, a, c);
22         a = mulMod(a, a, c);
23         b >>= 1;
24     }
25     return res;
26 }
27 
28 bool isPrime(LL n) {
29     if (n <= 1) return false;
30     if (n == 2) return true;
31     if (n & 1 == 0) return false;
32     srand((LL)time(0));
33     LL u = n - 1, k = 0, pre;
34     while (!(u&1)) u >>= 1, k++;
35     for (int t = 0; t < 10; t++) {
36         LL a = rand() % (n - 2) + 2;
37         LL ans = powMod(a, n - 1, n);
38         for (int i = 0; i < k; i++) {
39             pre = ans;
40             ans = mulMod(ans, ans, n);
41             if (ans == 1 && (pre != 1 && pre != n - 1)) return false;
42             pre = ans;
43         }
44         if (ans != 1) return false;
45     } 
46     return true;
47 }
48 
49 int main(void) {    
50     ios::sync_with_stdio(false);
51     int T;
52     cin >> T;
53     while (T--) {
54         LL n, k;
55         cin >> n >> k;
56         if (n < 2 * k) {
57             cout << "No" << endl;
58         } else {
59             if (k == 1) {
60                 if (isPrime(n)) cout << "Yes" << endl;
61                 else cout << "No" << endl;
62             } else if (k == 2) {
63                 if (n % 2 == 0) cout << "Yes" << endl;
64                 else if (isPrime(n - 2)) cout << "Yes" << endl;
65                 else cout << "No" << endl;
66             } else {
67                 cout << "Yes" << endl;
68             }
69         }
70     }
71     return 0;
72 }