用简单循环解决的素数问题

素数探求

试商法

//用2~sqrt(x)之间的整数去试商
int IsPrime(int x)
{
    int i,squareroot;
    if(x==1) return 0;
    squareroot=(int)sqrt(x);
	int i;
	for(i=2;i<=squareroot;i++)
    {
        if(x%i==0) return 0;
    }
	return 1;
}

判断完数

试商法

int IsPnumber(int x)
{
    int i,sum=0;
    for(i=1;i<=(x/2);i++)
    {
		if(x&i==0) sum+=i;
    }
    return x==sum?1:0;
}
//优化速度
int IsPnumber(int x)
{
    int i,sum=0;
    int k=(int)sqrt(x);
    for(i=1;i<=k;i++)
    {
		if(x&i==0)
        {
			sum=sum+i+x/i;
        }
    }
    return x==sum?1:0;
}

验证歌德巴赫猜想

任何一个大于等于6的偶数总能表示为两个素数之和

试商法

函数不能嵌套定义，但可以嵌套调用

引用标志变量flag 标记解是否找到的状态 一般情况下flag为0或1 flag注意要进行初始化

回文素数

1. 从10试到n-1
2. 分离个位，十位，百位
3. 若(t==m)&& IsPrime(m)则为回文素数
4. 2位与3位运算不同

孪生素数 相差为2的两个素数

1. IsPrime(i) && IsPrime(i+2)

   加速：若min为偶数，则min++，宁且i+=2;(测试所有奇数)

2. 使用front记录前一个素数

梅森素数

注意：pow()函数返回值为double，且调用较慢

最好自己写一个乘方函数