题目134：求与任意质数对相关的最小质数
Prime pair connectionConsider the consecutive primes p1 = 19 and p2 = 23. It can be verified that 1219 is the smallest number such that the last digits are formed by p1 whilst also being divisible by p2.
In fact, with the exception of p1 = 3 and p2 = 5, for every pair of consecutive primes, p2 > p1, there exist values of n for which the last digits are formed by p1 and n is divisible by p2. Let S be the smallest of these values of n.
Find ∑ S for every pair of consecutive primes with 5 ≤ p1 ≤ 1000000.
题目：
考虑两个连续质数 p1 = 19 和 p2 = 23。可以证明 1219 是具有如下性质的最小数字：该数字的最后部分由 p1 组成，同时该数字能够被 p2 整除。
事实上，除了 3 和 5，对于每一对连续质数，p2 > p1，都存在一个具有上述性质的数字 n。令 S 为这些 n 之中最小的数。
对于 5 ≤ p1 ≤ 1000000，求所有连续质数对的 S 之和。
估计要跑4~5个小时
from math import log10
from numba import jit
primes=*1000000
primes[:2]=*2
for i,prime in enumerate(primes):
if prime:
for j in range(i*i, 1000000, i):
primes=False
plist =
@jit
def solve():
S = 0
for i in range(1, len(plist)):
p1 = plist
p2 = plist
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 于 2022-9-1 20:02 编辑
/*
答案：18613426663617118
耗时：9.44929 (AMD 5600G)
*/
#include <iostream>
#include <vector>
#include <cstring>
#include <cmath>
#include <omp.h>
using namespace std;
char cp;//记录1000000以下的素数位置
vector<int> vp;//记录1000000以下的素数
int main(void)
{
//应用筛法求出素数的位置
memset(cp, 1, sizeof(cp));
cp = 0;
cp = 0;
for (int i = 2; i <= 1001; ++i)
{
if (cp == 0)
continue;
for (int j = i * i; j <= 1002001; j += i)
cp = 0;
}
//记录素数
for (int i = 5; i <= 1002001; ++i)
{
if (cp == 1)
vp.push_back(i);
}
//求出1000000以下的素数个数
int nK = (int)vp.size() - 1;
while (vp > 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, p2 = vp;
//求出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;
}
本题用OpenACC编程也非常简单，将上面的代码作很小的修改即可。
/*
答案：18613426663617118
耗时：6.2234 (GTX970)
*/
#include <iostream>
#include <cstring>
#include <openacc.h>
using namespace std;
char cp;//记录1000000以下的素数位置
int vp;//记录1000000以下的素数
int main(void)
{
//应用筛法求出素数的位置
memset(cp, 1, sizeof(cp));
cp = 0;
cp = 0;
for (int i = 2; i <= 1001; ++i)
{
if (cp == 0)
continue;
for (int j = i * i; j <= 1002001; j += i)
cp = 0;
}
//记录素数
int nK = 0;
for (int i = 5; i <= 1002001; ++i)
{
if (cp == 1)
vp = i;
}
--nK;
//出1000000以下的素数个数
while (vp > 1000000)
--nK;
unsigned long long nS = 0;
#pragma acc kernels loop reduction(+:nS)
for (int i = 0; i <= nK; ++i)//枚举连续的素数对
{
int p1 = vp, p2 = vp;
//求出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;
}
页:
[1]