lightOJ 1197 Help Hanzo （区间找素数）

lightOJ 1197 Help Hanzo （区间找素数）

​​http://lightoj.com/volume_showproblem.php?problem=1197​​

大意：区间找素数。 区间a and b (1 ≤ a ≤ b < 231, b - a ≤ 100000).

分析：发现一个特点，a和b的数字都特别大，但是b-a倒是挺小的，从这里做文章。

找出1——1e6之间的素数，对a——b之间素数筛选，结果记录在一个长度是1e5的数组tag里，由此空间复杂度的问题解决了。另外筛选也是有技巧的，一个素数筛选应是人为设定筛选起点：max(a/prim[i]*prim[i],prim[i]*prim[i])，然后不断加上素数，淘汰非素数。

不要简单认为这个句子知识简单的节省了时间，它保证了正确性。如1——10。第一个素数2，如果仅仅取起点a/prim[i]*prim[i]，那么2本身也被误认为是非素数。

#include #include #include using namespace std;const int N=1e6+10;typedef long long LL;LL prim[N],cnt;bool vis[N];bool tag[N/10+10];void getprim(){ for(LL i=2;i=a) tag[j-a]=1; } LL len=b-a; int ans=0; for(int i=0;i<=len;i++){ if(tag[i]==0) ans++; //printf("%d: %d\n",i+a,tag[i]); } if(a==1) ans--; printf("Case %lld: %lld\n",ca++,ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。