题目134：求与任意质数对相关的最小质数

欧拉计划

Prime pair connection

Consider the consecutive primes p₁ = 19 and p₂ = 23. It can be verified that 1219 is the smallest number such that the last digits are formed by p₁ whilst also being divisible by p₂.

In fact, with the exception of p₁ = 3 and p₂ = 5, for every pair of consecutive primes, p₂ > p₁, there exist values of n for which the last digits are formed by p₁ and n is divisible by p₂. Let S be the smallest of these values of n.

Find ∑ S for every pair of consecutive primes with 5 ≤ p₁ ≤ 1000000.

题目：

考虑两个连续质数 p₁ = 19 和 p₂ = 23。可以证明 1219 是具有如下性质的最小数字：该数字的最后部分由 p₁ 组成，同时该数字能够被 p₂ 整除。

事实上，除了 3 和 5，对于每一对连续质数，p₂ > p₁，都存在一个具有上述性质的数字 n。令 S 为这些 n 之中最小的数。

对于 5 ≤ p₁ ≤ 1000000，求所有连续质数对的 S 之和。

jerryxjr1220

估计要跑4~5个小时

1. from math import log10
   
2. from numba import jit
   
3. primes=[True]*1000000
   
4. primes[:2]=[False]*2
   
5. for i,prime in enumerate(primes):
   
6.         if prime:
   
7.                 for j in range(i*i, 1000000, i):
   
8.                         primes[j]=False
   
9. plist = [k for k,trueprime in enumerate(primes) if trueprime and k >=5]
   
10. 
    
11. @jit
    
12. def solve():
    
13.         S = 0
    
14.         for i in range(1, len(plist)):
    
15.                 p1 = plist[i-1]
    
16.                 p2 = plist[i]
    
17.                 k = 1
    
18.                 s = (10**(int(log10(p1))+1))*k+p1
    
19.                 while s % p2:
    
20.                         k += 1
    
21.                         s = (10**(int(log10(p1))+1))*k+p1
    
22.                 else:
    
23.                         S += s
    
24.         return S
    
25. print(solve())

复制代码

guosl

1. /*
   
2. 答案：18613426663617118
   
3. 耗时：9.44929 (AMD 5600G)
   
4. */
   
5. #include <iostream>
   
6. #include <vector>
   
7. #include <cstring>
   
8. #include <cmath>
   
9. #include <omp.h>
   
10. using namespace std;
    
11. 
    
12. char cp[1002004];//记录1000000以下的素数位置
    
13. vector<int> vp;  //记录1000000以下的素数
    
14. 
    
15. int main(void)
    
16. {
    
17.   //应用筛法求出素数的位置
    
18.   memset(cp, 1, sizeof(cp));
    
19.   cp[0] = 0;
    
20.   cp[1] = 0;
    
21.   for (int i = 2; i <= 1001; ++i)
    
22.   {
    
23.     if (cp[i] == 0)
    
24.       continue;
    
25.     for (int j = i * i; j <= 1002001; j += i)
    
26.       cp[j] = 0;
    
27.   }
    
28.   //记录素数
    
29.   for (int i = 5; i <= 1002001; ++i)
    
30.   {
    
31.     if (cp[i] == 1)
    
32.       vp.push_back(i);
    
33.   }
    
34.   //求出1000000以下的素数个数
    
35.   int nK = (int)vp.size() - 1;
    
36.   while (vp[nK] > 1000000)
    
37.     --nK;
    
38.   unsigned long long nS = 0;
    
39. #pragma omp parallel for firstprivate(nK) shared(vp) reduction(+:nS) schedule(dynamic,18)
    
40.   for (int i = 0; i <= nK; ++i)//枚举连续的素数对
    
41.   {
    
42.     int p1 = vp[i], p2 = vp[i + 1];
    
43.     //求出p1的位数
    
44.     int b = 1, nTemp = p1;
    
45.     while (nTemp != 0)
    
46.     {
    
47.       b *= 10;
    
48.       nTemp /= 10;
    
49.     }
    
50.     //求出最小满足条件的数
    
51.     unsigned long long y = p2 - p1;
    
52.     while ((y % b) != 0)
    
53.     {
    
54.       y += p2;
    
55.     }
    
56.     nS += y + p1;
    
57.   }
    
58.   cout << nS << endl;
    
59.   return 0;
    
60. }
    

复制代码

guosl

本题用OpenACC编程也非常简单，将上面的代码作很小的修改即可。

1. /*
   
2. 答案：18613426663617118
   
3. 耗时：6.2234 (GTX970)
   
4. */
   
5. #include <iostream>
   
6. #include <cstring>
   
7. #include <openacc.h>
   
8. using namespace std;
   
9. 
   
10. char cp[1002004];//记录1000000以下的素数位置
    
11. int vp[1002004];  //记录1000000以下的素数
    
12. 
    
13. int main(void)
    
14. {
    
15.   //应用筛法求出素数的位置
    
16.   memset(cp, 1, sizeof(cp));
    
17.   cp[0] = 0;
    
18.   cp[1] = 0;
    
19.   for (int i = 2; i <= 1001; ++i)
    
20.   {
    
21.     if (cp[i] == 0)
    
22.       continue;
    
23.     for (int j = i * i; j <= 1002001; j += i)
    
24.       cp[j] = 0;
    
25.   }
    
26.   //记录素数
    
27.   int nK = 0;
    
28.   for (int i = 5; i <= 1002001; ++i)
    
29.   {
    
30.     if (cp[i] == 1)
    
31.       vp[nK++] = i;
    
32.   }
    
33.   --nK;
    
34.   //出1000000以下的素数个数
    
35.   while (vp[nK] > 1000000)
    
36.     --nK;
    
37.   unsigned long long nS = 0;
    
38.   #pragma acc kernels loop reduction(+:nS)
    
39.   for (int i = 0; i <= nK; ++i)//枚举连续的素数对
    
40.   {
    
41.     int p1 = vp[i], p2 = vp[i + 1];
    
42.     //求出p1的位数
    
43.     int b = 1, nTemp = p1;
    
44.     while (nTemp != 0)
    
45.     {
    
46.       b *= 10;
    
47.       nTemp /= 10;
    
48.     }
    
49.     //求出最小满足条件的数
    
50.     unsigned long long y = p2 - p1;
    
51.     while ((y % b) != 0)
    
52.     {
    
53.       y += p2;
    
54.     }
    
55.     nS += y + p1;
    
56.   }
    
57.   cout << nS << endl;
    
58.   return 0;
    
59. }
    

复制代码