ACM刷题之路（二十一）大素数筛选 2019暑期集训 POJ 2689 Prime Distance

待我称王封你为后i 2024-02-19 20:39 61阅读 0赞

[题目链接：传送门][Link 1]

Sample Input

2 17
    14 17

Sample Output

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

**题目大致意思**就是：**告诉你一个s和e，求s和e之间靠的最近的两素数和离得最远的两素数，如果没有就输出There are no adjacent primes.这一句话。s和e范围为小于2,147,483,647的正整数，并且e和s最大相差不超过100W.**

**分析**：首先我们不能直接去求出2到2,147,483,647的全部素数，我们不可能开21E的数组，但是我们可以**求出2到sqrt（2,147,483,647）的素数表，并且根据这个来求2到2,147,483,647的全部素数。**

举个例子，

**我们如果知道1到10的素数：2 、3、 5、 7**

**那么我们可以通过这四个数，推出1到10^2的全部素数**，因为1~100的所有数，如果是合数，那么至少有2、3、5、7因子之一

比如91 =13 \* 7 有7

比如 81 = 9 \* 9 有9

等等

那么以此类推，**我们可以根据2到sqrt（2,147,483,647）的素数 来推出 2到2,147,483,647的全部素数。**

当然题目输入s和e，我们只需要推出s到e的素数即可。

**比如 s = 100W，e = 101W.**

**我们就从小素数表的2开始 把 100W 100W+2 100W+4 .。。。。。 101W-2 101W 筛掉**

**接着再3 从可以整除3的，并且大于等于s的第一个数开始。。。**

**接下去5 .。。一直到sqrt(e)为止。。。**

这绝对是一个好的创举！

解题的核心思想就是这个 ，接下来贴代码：

个人原创手打，不喜勿喷

#include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<cmath>
    using namespace std;
    const int MAXX = 46343;
    const int BIG = 1000000 + 7;
    bool isprime[MAXX];
    int smallprime[MAXX], len1;
    bool bigisprime[BIG];
    int bigprime[BIG / 4], len2;
    void init() {
    	len1 = 0;
    	memset(isprime, true, sizeof(isprime));
    	isprime[1] = false;
    	for (int i = 2; i < MAXX; i++) {
    		if (isprime[i]) {
    			smallprime[len1++] = i;
    			for (int j = i + i; j < MAXX; j += i) {
    				isprime[j] = false;
    			}
    		}
    	}
    }
    void run(int s, int e) {
    	len2 = 0;
    	if (s < 2)s = 2;
    	memset(bigisprime, true, sizeof(bigisprime));
    	int k = (int)sqrt(0.0 + e) + 1;
    	for (int i = 0; i < len1 && smallprime[i] < k; i++){
    		int t = s / smallprime[i];
    		if (t * smallprime[i] < s) t++;
    		if (t < 2) t = 2;
    		for (int j = t; (long long)j * smallprime[i] <= e; j++) {
    			bigisprime[j * smallprime[i] - s] = false;
    		}
    	}
    	for (int i = 0; i <= e - s; i++) {
    		if (bigisprime[i]) {
    			bigprime[len2++] = i + s;
    		}
    	}
    }
    int main()
    {
    	init();
    	int s, e;
    	while (~scanf_s("%d%d", &s, &e)) {
    		int maxx = -1, minn = 999, mas, mae, mis, mie;
    		run(s, e);
    		if (len2 < 2) {
    			puts("There are no adjacent primes.");
    		}
    		else {
    
    			for (int i = 1; i < len2 && bigprime[i] <= e; i++) {
    				int index = bigprime[i] - bigprime[i - 1];
    				if (index < minn) {
    					mis = bigprime[i - 1];
    					mie = bigprime[i];
    					minn = index;
    				}
    				if (index > maxx) {
    					mas = bigprime[i - 1];
    					mae = bigprime[i];
    					maxx = index;
    				}
    			}
    			printf("%d,%d are closest, %d,%d are most distant.\n", mis, mie, mas, mae);
    		}
    	}
    	return 0;
    }

[Link 1]: http://poj.org/problem?id=2689