本文主要是介绍5.预处理和筛选法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
预处理适合输入组数比较大,数据量比较大的问题。不预处理容易超时,可以先把所有结果存入数组,然后对于每组输入直接从数组里取答案,就不用每个输入都算一遍,大大提高了效率。
筛选法:
注意:每一组上限n只需筛选到根号n就可以了,因为往后的数前面已经筛选过,根号n乘根号n等于n,已经到上限。再往上乘就不在范围内了。这种情况有很多,一定要注意效率。
而对于每一个“最小素数n”,只需从n的n倍开始筛出,因为比n小的倍数在前面的“最小素数”里已经筛选过。
筛选法求n以内素数代码:
#include<stdio.h>
#include<math.h>
int a[100001];
int main()
{ int i,j,n;while(scanf("%d",&n)==1){ for(i=2;i<=n;i++){if(a[i]==0)for(j=i+i;j<=n;j+=i)a[j]=1; }printf("2");for(i=3;i<=n;i++)if(a[i]==0) printf(" %d",i); printf("\n"); }return 0; }
这篇关于5.预处理和筛选法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!