首页 > 代码库 > POJ2689_Prime Distance【素数】【两次筛法】

POJ2689_Prime Distance【素数】【两次筛法】

2024-07-24 06:35:39   215人阅读

Prime Distance
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 12644Accepted: 3369
Description


The branch of mathematics called number theory is about properties of numbers. One of the areas that has captured the interest of number theoreticians for thousands of years is the question of primality. A prime number is a number that is has no proper factors (it is only evenly divisible by 1 and itself). The first prime numbers are 2,3,5,7 but they quickly become less frequent. One of the interesting questions is how dense they are in various ranges. Adjacent primes are two numbers that are both primes, but there are no other prime numbers between the adjacent primes. For example, 2,3 are the only adjacent primes that are also adjacent numbers. 
Your program is given 2 numbers: L and U (1<=L< U<=2,147,483,647), and you are to find the two adjacent primes C1 and C2 (L<=C1< C2<=U) that are closest (i.e. C2-C1 is the minimum). If there are other pairs that are the same distance apart, use the first pair. You are also to find the two adjacent primes D1 and D2 (L<=D1< D2<=U) where D1 and D2 are as distant from each other as possible (again choosing the first pair if there is a tie).
Input


Each line of input will contain two positive integers, L and U, with L < U. The difference between L and U will not exceed 1,000,000.
Output


For each L and U, the output will either be the statement that there are no adjacent primes (because there are less than two primes between the two given numbers) or a line giving the two pairs of adjacent primes.
Sample Input


2 17
14 17
Sample Output


2,3 are closest, 7,11 are most distant.
There are no adjacent primes.
Source


Waterloo local 1998.10.17

题目大意：给你一个区间【L,U】,求出从L到U之间素数序列中，连续两个素数差值最大

的最小的两对素数对，但其中(1<=L< U<=2,147,483,647)，但区间【L，U】距离不超

过1000000

思路：因为L，U的值太大了，普通素性判断和素数筛法都不可行，所以可以考虑先筛选

一次，筛出50000以内的素数，然后用50000以内的素数再次筛选出区间【L，U】的素

数。第一次素数筛法比较简单，主要是第二次筛法，分别判断【L,U】中每个数是50000

以内的素数的多少倍，若为1倍，则从2倍开始筛选。若不为1倍，则考虑是否是整数倍，

若为整数倍，则从整数倍开始筛，否则从下1倍开始筛选

比如【L,U】为【50000,60000】，则50000为2的250000倍，应从2的25000倍筛选，

也就是50000,50002,50004,50006……筛去。

若【L,U】为【50001,60000】，则50001不为2的整数倍，应从2的250001倍筛选，也

就是50002,50004,50006……筛去。

参考博文：http://blog.csdn.net/returnzero__/article/details/7835655

#include<stdio.h>
#include<string.h>
bool Prime[50010];
int Primer[1000010];
bool Prime1[1000010];
int IsPrime()//第一次筛50000内的素数
{
    int num = 0;
    for(int i = 2; i <= 50000; i++)
        Prime[i] = true;
    for(int i = 2; i <= 50000; i++)
    {
        if(Prime[i])
        {
            Primer[num++] = i;
            for(int j = i+i; j <= 50000; j+=i)
            {
                Prime[j] = false;
            }
        }
    }
    return num;
    //num为50000范围内的素数个数
}

int solve(__int64 a,__int64 b)
/*
在第一次筛素数的基础上，利用50000以内的素数，筛去范围【a,b】之间的素数倍数，
剩下则为素数
*/
{
    int num = IsPrime();
    memset(Prime1,true,sizeof(Prime1));//Prime1数组用来存放范围【a,b】的素性判断

    if(a == 1)//这里注意1不是素数
        Prime1[0] = 0; //这里表示0+1不为素数

    for(__int64 i = 0; i < num && Primer[i] * Primer[i] <= b; i++)
    {
        __int64 begin = a/Primer[i] + (a%Primer[i] != 0);
        //上边的a/Primer算出应a为素数Primer[i]的多少倍
        //(a%Primer[i]!=0)表示应从Primer[i]的a/Primer[i]倍开始筛，还是a/Primer[i]+1倍筛
        if(begin == 1)//若得出结果为所被筛素数的1倍，则从该素数的2倍开始筛
            begin++;

        for(begin = begin*Primer[i]; begin <= b; begin += Primer[i])
            Prime1[begin - a] = false;
    }

    //这里重新利用Primer数组，用来存放区间【a,b】间的素数，num为素数个数
    memset(Primer,0,sizeof(Primer));
    num = 0;
    for(__int64 i = a; i <= b; i++)
    {
        if(Prime1[i-a]==1)
        {
            Primer[num++] = i-a;
        }
    }
    return num;
}

int main()
{
    __int64 a,b;

    __int64 posa1,posb1,posa2,posb2;
    while(~scanf("%I64d%I64d",&a,&b))
    {
        __int64 Max = -2147483647,Min = 2147483647;
        int num = solve(a,b);
//        for(__int64 i = 0; i < num; i++)
//            printf("%I64d ",Primer[i]+a);
        if(num <= 1)
        {
            printf("There are no adjacent primes.\n");
            continue;
        }
        for(int i = 0; i < num-1; i++)//这里i+1范围为1到num-1，则i范围为0到num-2，之前一直错在这里
        {
            if(Primer[i+1]-Primer[i] < Min)
            {
                Min = Primer[i+1] - Primer[i];
                posa1 = Primer[i];
                posb1 = Primer[i+1];
            }
            if(Primer[i+1]-Primer[i] > Max)
            {
                Max = Primer[i+1] - Primer[i];
                posa2 = Primer[i];
                posb2 = Primer[i+1];
            }
        }

        printf("%I64d,%I64d are closest, %I64d,%I64d are most distant.\n",posa1+a,posb1+a,posa2+a,posb2+a);
    }
    return 0;
}


POJ2689_Prime Distance【素数】【两次筛法】


联系
我们