数据结构与算法实验题素数区间

逃离我推掉我的手 2022-04-14 06:58 198阅读 0赞

★实验任务  
dark di 在做数学题目的时候发现了一个现象，2 个相邻的素数之间存在一  
个区间，他把这个区间称为非素数区间，那么 dark di 想知道，给定一个正整数  
x，x 所在的非素数区间长度是多少呢？  
例如 23 和 29 是 2 个相邻的素数，他们之间的非素数区间是\[24,28\]，长度  
是 5，假设 x=27，那么 x 所在的非素数区间长度就是 5。如果 x 是一个素数，则  
答案是 0。  
注意：素数指的是除了 1 和它本身以外不再有其他因数的自然数。

★数据输入  
第一行输入一个正整数 T，表示接下去有 T 次询问。  
接下去 T 行，每行一个正整数 x。(x<=100000)。  
对于 30%的数据，T<=5，x<=100  
对于 80%的数据，T<=10，x<=5000  
对于 100%的数据，T<=100000，x<=100000

★数据输出  
输入 T 行，每行一个整数表示非素数区间的长度。  
输入示例  
2  
27  
1  
输出实例  
5  
0

分析：  
这题的重点有两个：如何判断一个数是不是素数；以及通过什么方法获得区间长度。  
1、关于判断素数的函数，最普通的就是这种写法：

bool is_prime(int number) { 
    	if (number <= 1) { 
    		return false;
    	}
    	for (int i = 2; i <= sqrt(number); i++) { 
    		if (number%i == 0) { 
    			return false;
    		}
    	}
    	return true;
    }

然而就是这种写法也有可以改进的地方：sqrt(number)是一个固定值，没必要每次循环完都要重新计算一次。所以，应该事先用一个变量sqr把sqrt(number)的值存起来，循环时这个sqr来判断。  
用这个方法在n比较小的时候，可以在给定的端点前后不断执行is\_prime函数，可在这题中10^5的情况下时间有可能不够。所以另外想办法，参考同学的优秀作业，可以使用“**素数筛**”的方法，具体如下（以下摘抄于这位同学的讲解PPT）：

可以提前用所谓的“素数筛”的方法，对范围内的所有数的是素数与否进行标记。具体操作过程如下：

顾名思义，就是要在给定范围的数内，筛出所有素数  
**从小到大枚举所有数，对每一个素数，筛去它的所有倍数**，剩下的就是素数了。可是一开始并不知道那些数是素数。  
没有关系，仅仅需要知道2是素数就足够了，

--------------------

例如：  
求1—15中所有素数  
筛去2的倍数  
2、3、4、5、6、7、8、9、10、11、12、13、14、15  
3之前没有被筛掉，所以3是素数，筛除3的倍数  
2、3、4、5、6、7、8、9、10、11、12、13、14、15  
4被筛去，则4不是素数，看5，5之前没被筛，则筛去5的倍数  
2、3、4、5、6、7、8、9、10、11、12、13、14、15  
6被筛去，看7。。。。。。  
直到遍历完15后，便得到了1–15的素数表

--------------------

我们可以申请一个长度为MAX的bool数组，false表示是未被筛除，true表示已被筛除。  
代码如下：

const int MAX=100010;
    bool PrimeNum[MAX]={ false};//将数组元素全初始化为false
    for (int i = 2; i < MAX; ++i) { 
    	if (PrimeNum[i] == false)//如果i是素数
    		for (int j = i + i; j < MAX; j += i)
    			PrimeNum[j] = true;//筛去i的倍数
    }

这样就得到了1～MAX-1之间的素数表，有了表以后，对于每次查询，只需查表即可，无需再执行isPrime函数，可以节省大量的时间。  
此法是典型的空间换时间的策略，消耗空间保存好素数结果后，便可处理查询次数T接近10^5的情况。