首页 > 代码库 > 筛选法求素数
筛选法求素数
一：素数的基本求法：
bool pd(int x){ if(x==1)return false; for(int i=2;i*i<=x;i++) if(x%i==0)return false; return true;}
二 筛选法求素数（简便快捷）：可以用事先筛选好的素数来判断一个数是否为素数。
1 int prime[5500],tot; 2 bool isprime[50001]; 3 void init()//先处理出50000以内的质数，可用来筛INT以内的质数 4 { 5 tot = 0; 6 memset(isprime, true, sizeof(isprime)); 7 prime[tot++] = 2; 8 for(int i = 3; i < 50000; i += 2) //素数只能是奇数（虽然有的奇数不满足但能在之前将isprime[i]置为false 9 {10 if(isprime[i]) {11 prime[tot++] = i;//素数本身是一定能赋值进去的，不用担心12 if(i * i < 50000) {13 for(int j = i + i; j < 50000; j += i) isprime[j] = false;14 }15 }16 }17 }
三 筛选法求素数的具体应用：
poj3090
题意：从原点看第一象限里的所有点，能直接看到的点的数目是多少。（不包含原点）
点（x，y）可见当且仅当x,y互质。
反证：若x,y存在公约数k>1。那么必然存在点（x/k,y/k），会挡住（x,y）。
问题就变成了：求1-N中，所有与N互质的数的个数。
这不就是欧拉函数....
so,ans=(euler(1)+euler(2)+...+euler(n))*2+1。
这就是简单的运用欧拉函数求解的问题了。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。