Bi-shoe and Phi-shoe LightOJ - 1370LightOJ

​​http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1370​​

兩個質數之間得合數得歐拉函數小于較小的質數 （暫時還沒想出證明）

這樣每個合數都可以被一個比它小的素數替代 是以隻考慮素數即可 對每個給定的數 找一個歐拉函數值大于該數的數 就相當于找第一個大于該數的素數

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=2e6;

int book[maxn],prime[maxn];
int tot;

void init()
{
    int i,j;
    book[1]=1;
    for(i=2;i*i<=2e6;i++){
        if(!book[i]){
            for(j=i+i;j<=2e6;j+=i){
                book[j]=1;
            }
        }
    }
    for(i=1;i<=2e6;i++){
        if(!book[i]) prime[++tot]=i;
    }
    for(i=1;i<=100;i++){
        printf("%d\n",prime[i]);
    }
}

int main()
{
    ll ans;
    int t,cas,n,p,val;
    init();
    scanf("%d",&t);
    for(cas=1;cas<=t;cas++){
        scanf("%d",&n);
        ans=0;
        while(n--){
            scanf("%d",&val);
            p=upper_bound(prime+1,prime+tot+1,val)-prime;
            ans+=prime[p];
        }
        printf("Case %d: %lld Xukha\n",cas,ans);
    }

    return 0;
}