Project Euler 357

题目

Prime generating integers

Consider the divisors of $30: 1,2,3,5,6,10,15,30$. It can be seen that for every divisor $d$ of $30$, $d+30/d$ is prime.

Find the sum of all positive integers $n$ not exceeding $100 000 000$ such that for every divisor $d$ of $n$, $d+n/d$ is prime.

解决方案

如果一个数$n$满足题目要求，那么$n$一定满足以下条件。

1. $n+1$一定是一个质数（因为每个数都有因子$1$，有$n+1=\dfrac{n}{1}+1$）
2. $n$是一个无平方因子数，如果存在一个质因子$p$，使得$p^2\mid n$，那么$p+\left(\dfrac{n}{p}\right)=p\cdot\left(1+\dfrac{n}{p^2}\right)$，那么此时的$p+\dfrac{n}{p}$不是质数。

对于这些满足条件的数，直接枚举它们的因数，判断答案合法性即可。

代码

# include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=100000000;
int v[N+4],pr[N],m=0;
bool is_square_free[N+4];
bool ok(int x){
    for(int i=1;i*i<=x;i++)
    if(x%i==0){
        int w=i+x/i;
        if(v[w]!=w) return 0;
    }
    return 1;
}
int main(){
    for(int i=2;i<=N+1;i++){
        if(v[i]==0) v[i]=i,pr[++m]=i,is_square_free[i]=1;
        for(int j=1;j<=m;j++){
            if(pr[j]>v[i]||pr[j]>(N+1)/i) break;
            v[i*pr[j]]=pr[j];
            is_square_free[i*pr[j]]=(v[i]==pr[j]?0:is_square_free[i]);
        }
    }
    ll ans=1;
    for(int i=2;i<=m;i++){
        int x=pr[i]-1;
        if(is_square_free[x]&&ok(x)) ans+=x;
    }
    printf("%lld\n",ans);
}