poj2909 || poj2262

#include <stdio.h>
#include <stdlib.h>
#include<math.h>
int isPri(int a, int b)
{
    int i;
    for(i=2; i <= sqrt(a); i++)
    {
        if(a%i == 0)
            return 0;
    }
    for(i=2; i <= sqrt(b); i++)
    {
        if(b%i == 0)
            return 0;
    }
    return 1;
}
int main()
{
    int n,flag,i,cout;
    while(scanf("%d",&n) != EOF && n)
    {
        cout=0;
        for(i=2; i< n/2+1; i++)
        {
            flag=isPri(i,n-i);
            if(flag == 1)
                cout++;
        }
        printf("%d
",cout);
    }
    return 0;
}

for循环用于产生数对，用i<n/2+1或i<=n/2都可以避免产生重复的数对

在判断素数的时候采用小学生做法：从2到sqrt(n),i=2,i<=n(必须加=)

如果是2和3，根本不会经过循环

以后都用《埃拉托斯特尼筛法》打表

算法描述：小于2的不是素数，用一个数组a[10000],元素下标表示这个数，元素的值表示是否是素数，c++做法是，bool a[10000],将a[0]和a[1]赋成0，从2开始，2*2,2*3...

2*6...这些下标对应的元素值全改0，在此环境下再次寻找下一个素数，再一次，3*2,3*3,3*4...乘积整体小于10000

ar[10000]
ar[0]=0;
ar[1]=0;
for(i=2;i<10000;i++)
{
    ar[i]=1;
}
for(i=2;i<10000;i++)
{
    if(ar[i] == 1)
    {
        for(j=2;i*j<10000;j++)
        {
            ar[i*j] = 0;
        }
    }
}

下面的动态图很清楚：

http://blog.csdn.net/kingwolfofsky/article/details/7199758