1 条题解

  • 0
    @ 2025-10-8 16:56:10
    #include<bits/stdc++.h>//这是100分代码
    using namespace std;
    typedef long long LL;
    int prime[1110000], pr, a[1110000], alen;bool v[1110000];
    int main()
    {
        pr=0;memset(v,0,sizeof(v));
        for(int i=2;i<=50000;i++)
        {
            if(v[i]==0)prime[++pr]=i;
            for(int j=1;j<=pr && i*prime[j]<=50000;j++)
            {
                v[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
        int l, r;
        while(scanf("%d%d", &l, &r)!=EOF) 
        {
            //把[l,r]区间内所有的合数用他们的最小质因子筛掉
            memset(v, 0, sizeof v);
            for (int i = 1; i <= pr;i++) 
            {
                LL p = prime[i];//(l + p - 1)也有可能超过int 
                for(LL j = max(2 * p, (l + p - 1) / p * p); j <= r; j += p)//最后一个j有可能超过int 
                    v[j - l] = 1;
            }
    
            //剩下的所有的都是素数了
            alen = 0;
            for (int i = 0; i <= r - l; i++ )
                if (!v[i] && i + l > 1)
                    a[++alen] = i + l;
    
            if (alen < 2) printf("There are no adjacent primes.\n");
            else 
            {
                //计算间隔
                int minp = 1, maxp = 1;
                for (int i = 1; i < alen;i++) 
                {
                    int d = a[i + 1] - a[i];
                    if (d < a[minp + 1] - a[minp]) minp = i;
                    if (d > a[maxp + 1] - a[maxp]) maxp = i;
                }
                printf("%d,%d are closest, %d,%d are most distant.\n", 
                a[minp], a[minp + 1], 
                a[maxp], a[maxp + 1]);
            }
        }
        return 0;
    }
    
    • 1

    信息

    ID
    1305
    时间
    1000ms
    内存
    128MiB
    难度
    7
    标签
    递交数
    185
    已通过
    47
    上传者