学步园

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).

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.

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.

2 17
14 17

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

Waterloo local 1998.10.17

两次素数筛选。

代码如下：

#include<iostream>
#include<string.h>
using namespace std;
bool mark[1000010]; //若给出的第i个数为素数，mark[i]=1，否则mark[i]=0
bool p[47001]; //若i为素数，则p[i]=1，否则p[i]=0
long long prime[47001]; //按照从小到大顺序存储47000以内的所有素数
long long number[1000010]; //按照从小到大顺序存储l~u内的所有素数

int main(void) {//第一次筛选，找出47000以内的素数，用这些素数就可以进行下一次筛选
    long long count = 0; //47000以内素数的个数
    memset(p, 1, sizeof (p)); //数组初始化
    p[0] = p[1] = 0; //0和1都不是素数
    for (long long i = 2; i <= 47000; i++) {
        if (p[i]) {
            prime[count++] = i; //如果i为素数，存入prime数组，count+1
            for (long long j = i * i; j <= 47000; j += i)
                p[j] = 0; //筛掉合数
        }
    }
    long long l, u; //给定的数字范围
    while (cin >> l >> u) {//读入数字范围
        memset(mark, 1, sizeof (mark)); //mark数组初始化
        if (l == 1)
            l = 2; //若l为1会影响后续第二次筛选，将所有的数都筛掉
        for (long long i = 0; prime[i] * prime[i] < u; i++) {
            //以prime[i]为因子的第一个非素数是prime[i]的多少倍
            long long k = l / prime[i];
            if (k * prime[i] < l)
                k++;
            if (k == 1)
                k++;
            for (long long j = k * prime[i]; j <= u; j += prime[i])
                mark[j - l] = 0; //筛掉合数，j-l是该数在给出数据范围中出现的顺序
        }
        long long prime_count = 0; //统计给出数据中素数的个数
        for (long long i = l; i <= u; i++)
            if (mark[i - l])
                number[prime_count++] = i; //将给出数据范围中的素数存入number数组中
        if (prime_count <= 1)
            cout << "There are no adjacent primes." << endl; //如果素数的个数小于等于1说明没有相邻的素数
        else {//确定相距最近和最远的素数
            long long ans1 = 0;
            long long ans2 = 0;
            for (long long i = 0; i < prime_count - 1; i++) {
                if (number[i + 1] - number[i] > number[ans1 + 1] - number[ans1])
                    ans1 = i;
                if (number[i + 1] - number[i] < number[ans2 + 1] - number[ans2])
                    ans2 = i;
            }
            cout << number[ans2] << ',' << number[ans2 + 1] << " are closest, " << number[ans1] << ',' << number[ans1 + 1] << " are most distant." << endl; //输出结果
        }
    }
    return 0;
}

code要全身心投入。