poj2262---素数(质数)的判断


收获:一开始以为是100万的所有数字,题目要求是只要偶数,也可以分析出来,如果是给一个奇数,当我们给他大于等于3的奇数(这个数加有可能不是质数,但至少满足是奇数,至于是不是质数还要自己判断),剪出来一定是个偶数,无论如何都给不出答案,但是,题目要求输入偶数,偶数可以=奇数+奇数

因此一定会出现:

20
3   5   7   9   11  13  15  17  19
17 15 13 11  9    7    5    3    1

i<=n/2就可以了

附带素数的筛选法:

http://download.csdn.net/detail/u012203889/6484529

discuss上有种先把表给打出来,然后查表的方法,很快

http://poj.org/showmessage?message_id=341336

暴力筛选素数的方法:

按理说是将一个数n从2开始,一直除到n-1,如果其中有能被整除的,那么就不是质数

优化下,开n的根,有这样一个定理:如果说n不能被x整除,那么n也不能被x^2整除

2是下限,根号n是上限,2到根号n之间的数如果都不诶整除,那么

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
int isPriOdd(int a,int b)
{
int i;
for(i=;i <= sqrt(a); i++)
{
if(a%i == )
return ;
}
return ;
for(i=;i <= sqrt(b); i++)
{
if(b%i == )
return ;
}
return ;
}
int main()
{
int n,tmp;
while(scanf("%d",&n) != EOF)
{
int b,i;
if(n==)
break;
for(i=;i<=n/;i+=)
{
b=n-i;
tmp=isPriOdd(i,b);
if(tmp == )
break;
}
printf("%d = %d + %d\n",n,i,b);
}
return ;
}
上一篇:AngularJS源码解析4:Parse解析器的详解


下一篇:MFC CTreeCtrl控件