题目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个小时

from math import log10
from numba import jit
primes=[True]*1000000
primes[:2]=[False]*2
for i,prime in enumerate(primes):
        if prime:
                for j in range(i*i, 1000000, i):
                        primes[j]=False
plist = [k for k,trueprime in enumerate(primes) if trueprime and k >=5]

@jit
def solve():
        S = 0
        for i in range(1, len(plist)):
                p1 = plist[i-1]
                p2 = plist[i]
                k = 1
                s = (10**(int(log10(p1))+1))*k+p1
                while s % p2:
                        k += 1
                        s = (10**(int(log10(p1))+1))*k+p1
                else:
                        S += s
        return S
print(solve())

guosl

/*
答案：18613426663617118
耗时：9.44929 (AMD 5600G)
*/
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <omp.h>
using namespace std;

char cp[1002004];//记录1000000以下的素数位置
vector<int> vp;  //记录1000000以下的素数

int main(void)
{
  //应用筛法求出素数的位置
  memset(cp, 1, sizeof(cp));
  cp[0] = 0;
  cp[1] = 0;
  for (int i = 2; i <= 1001; ++i)
  {
    if (cp[i] == 0)
      continue;
    for (int j = i * i; j <= 1002001; j += i)
      cp[j] = 0;
  }
  //记录素数
  for (int i = 5; i <= 1002001; ++i)
  {
    if (cp[i] == 1)
      vp.push_back(i);
  }
  //求出1000000以下的素数个数
  int nK = (int)vp.size() - 1;
  while (vp[nK] > 1000000)
    --nK;
  unsigned long long nS = 0;
#pragma omp parallel for firstprivate(nK) shared(vp) reduction(+:nS) schedule(dynamic,18)
  for (int i = 0; i <= nK; ++i)//枚举连续的素数对
  {
    int p1 = vp[i], p2 = vp[i + 1];
    //求出p1的位数
    int b = 1, nTemp = p1;
    while (nTemp != 0)
    {
      b *= 10;
      nTemp /= 10;
    }
    //求出最小满足条件的数
    unsigned long long y = p2 - p1;
    while ((y % b) != 0)
    {
      y += p2;
    }
    nS += y + p1;
  }
  cout << nS << endl;
  return 0;
}

guosl

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

/*
答案：18613426663617118
耗时：6.2234 (GTX970)
*/
#include <iostream>
#include <cstring>
#include <openacc.h>
using namespace std;

char cp[1002004];//记录1000000以下的素数位置
int vp[1002004];  //记录1000000以下的素数

int main(void)
{
  //应用筛法求出素数的位置
  memset(cp, 1, sizeof(cp));
  cp[0] = 0;
  cp[1] = 0;
  for (int i = 2; i <= 1001; ++i)
  {
    if (cp[i] == 0)
      continue;
    for (int j = i * i; j <= 1002001; j += i)
      cp[j] = 0;
  }
  //记录素数
  int nK = 0;
  for (int i = 5; i <= 1002001; ++i)
  {
    if (cp[i] == 1)
      vp[nK++] = i;
  }
  --nK;
  //出1000000以下的素数个数
  while (vp[nK] > 1000000)
    --nK;
  unsigned long long nS = 0;
  #pragma acc kernels loop reduction(+:nS)
  for (int i = 0; i <= nK; ++i)//枚举连续的素数对
  {
    int p1 = vp[i], p2 = vp[i + 1];
    //求出p1的位数
    int b = 1, nTemp = p1;
    while (nTemp != 0)
    {
      b *= 10;
      nTemp /= 10;
    }
    //求出最小满足条件的数
    unsigned long long y = p2 - p1;
    while ((y % b) != 0)
    {
      y += p2;
    }
    nS += y + p1;
  }
  cout << nS << endl;
  return 0;
}