阜阳市住房和城乡建设部网站,域名有永久的吗,湖南微信小程序开发制作,贵阳市做网站公司求素数是比较基本的内容#xff0c;有时候我们会需要打一个素数表。一般如果n比较小我们会使用#xff08;%2~sqrtn#xff09;这种算法#xff0c;简单但是时间耗费很多#xff0c;复杂度是O(n^2)。这里介绍一种筛选求素数法#xff0c;基本要点是#xff0c;如果找到一… 求素数是比较基本的内容有时候我们会需要打一个素数表。一般如果n比较小我们会使用%2~sqrtn这种算法简单但是时间耗费很多复杂度是O(n^2)。这里介绍一种筛选求素数法基本要点是如果找到一个素数如3那么就往后筛出所有3的倍数。 一般筛选求素数 void init()
{memset(prim, true, sizeof(prim));for (int i 2; i*i maxn; i){if (prim[i]) //如果是素数就把其倍数全删掉for (int j i; i*j maxn; j)//j从i开始可以避免一部分重复prim[i*j] false;}
}这个方法比一般的打表法快但运算中间有大量重复如i2时筛除302*15但i5时筛除305*6重复的标示了。 void init()
{for (int i 2; i maxn; i){if (!map[i]){for (int j i; j maxn; ji)map[j] map[j / i] 1; //这样还可以统计i由几个素因子构成}}
} 线性筛选求素数 void init()
{memset(notprim, false, sizeof(notprim));int cnt 0;for (int i 2; i maxn; i){if (!notprim[i]) prim[cnt] i; //如果是素数直接赋值for (int j 0; j cnti*prim[j] maxn; j)//如果是合数将前面所有的素数乘当前i筛去{notprim[i*prim[j]] true;if (i%prim[j] 0) //关键处:如果当前合数中出现前面已经出现的素数就跳出break;}}
} 首先要明确所有合数都可以由素数相乘得到。 所以如果 i 是合数此时 i 可以表示成递增素数相乘 ip1*p2*...*pn, pi都是素数2in pipj ( ij )p1是最小的系数。 根据“关键处”的定义当p1prim[j] 的时候筛除就终止了也就是说只能筛出不大于p1的质数*i。 我们可以直观地举个例子。i2*3*5此时能筛除 2*i ,不能筛除 3*i如果能筛除3*i 的话当 i 等于 i3*3*5 时筛除2*i 就和前面重复了。 例子POJ2909 题目要求输入一个数输出有几种方案使这个数能等于两个素数相加 15362476Seasonal2909Accepted212K0MSC646B2016-04-07 08:09:05#includestdio.h
#includestdlib.h
#includestring.h
#define maxn 214
bool notprim[maxn];
int prim[maxn];void init()
{memset(notprim, false, sizeof(notprim));int cnt 0;for (int i 2; i maxn; i){if (!notprim[i]) prim[cnt] i; //如果是素数直接赋值for (int j 0; j cnti*prim[j] maxn; j)//如果是合数将前面所有的素数乘当前i筛去{notprim[i*prim[j]] true;if (i%prim[j] 0) //关键处:如果当前合数中出现前面已经出现的素数就跳出break;}}
}int main()
{int n;init();while (scanf(%d, n), n){int num 0;for (int i 2; i * 2 n; i)if (!notprim[i] !notprim[n - i])num;printf(%d\n, num);}return 0;
}转载于:https://www.cnblogs.com/seasonal/p/10343791.html
