素数变型题
老规矩,想把代码写正确的第一步就是先不要着急写代码
跟着我审题,建立逻辑
1.题目很短(输出从小到大的第 k 个质数。)很容易就知道题目要求我们输出从第k个素数,也就是输入一个k找到从小到大所有素数排列中的第k个素数
2.输入多组测试就不说了,练了很多了
3.我们跟定要用到筛素数的逻辑模型,进行改写,又因为数据量很大所以我们用最优化的模型(去偶开根号法)
改写细节(1):去偶开根号是从3开始运行的所以需要循环前特判,提前把2这个唯一的偶数中的素数先预处理了
改写细节(2):由于是输入一个k,让找出第k个素数,所以筛素数的结束条件就不是i<=n,所以第一个for循环就删除判断条件,让他一直循环下去
改写细节(3):无限循环的结束条件就是找到第k个素数为止,因此需要定义一个计数器,筛出一个素数就累加一个,直到计数器等于k的时候,也就是找到了第k个素数,就结束整个循环,并输出i值即可,因此整个循环的结束情况跟k成正比,所以如果k输入的越大就可能导致时间开销越大,所以我一开始就选择用去偶开根号法,但是
改写细节(4):最后就是把筛素数模型的输出变成计数器累加即可
ok,逻辑搞明白了,看看代码吧
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
bool judge(int n)
{
for (int i = 2; i <= sqrt(n); i ++)
if(n % i == 0) return 0;
return 1;
}
int main()
{
int k;
while (~scanf("%d", &k))
{
//筛出一个质数就累加一个,计数器功能
int count = 0;
//筛素数的模型
if(k >= 1) //改写细节(1)
count = 1;
else
{
printf("2\n");
break;
}
for(int i = 3;;i += 2 ) //改写细节(2)
{
int flag = 1;
int tmp = sqrt(i);
for(int j = 2;j <= tmp;j ++)
if(i % j == 0)
flag = 0;
if(flag) //改写细节(4)
count ++;
if(count == k) //改写细节(3)
{
printf("%d\n",i);
break; //结束循环
}
}
}
return 0;
}
以上的思路属于基于逻辑模型必须会的朴素写法,但是这道题很特殊,数据量k值给的特别大,而且我们每一次都要从重新筛一遍素数,如果给我们的测试数据特别多了的话,那就可能导致比O(n^2)还要大的时间复杂度,所以时间复杂度还是非常高,很多样例都超时了,因此我们在学一种新的常用思想:预处理
我们要尽可能的减少循环次数最好的办法就是用空间换时间:
思想:我们提前按照数据范围给定的大小来设置一个很大的数组,然后套用筛素数的模型在输入测试数据之前,把所有给定很大范围内的所有素数全部提前筛选出来,并且依次存放在数组里面,这样随便输入多少个k,我们都可以利用数组瞬间索引到,这样时间复杂度就瞬间降下来了
具体实现很简单,自己看吧,一定要学会这种思想,空间换时间的方法还有很多:
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
//提前把所有素数筛出来,并按顺序依次存放在数组里
int prime[10100];
int main()
{
int num = 0,i,j; //num就相当于素数的计数器,筛出一个记录一个
int n = 105000; //照着题目给定的范围尽可能的开
//其实就相当于把1~n(n尽可能大的范围)的所有素数全部提前筛出来存好
for(i = 2; i <= n; i ++)
{
int flag = 1;
for(j = 2; j <= sqrt(i); j ++)
if( i % j == 0 ) flag = 0;
if(flag)
prime[num ++] = i; //记录素数,并且按顺序存放
}
int k;
while(~scanf("%d",&k))
{
printf("%d\n",prime[k-1]);
}
return 0;
}