UC知道筛法求素数
来源：百度知道 编辑：UC知道 时间：2024/09/25 13:18:12
我写得求100以内的素数怎么最后99和100冒出来了？
求求哪位高手帮忙找找错！急用！
#include <cstdlib>
#include <iostream>
using namespace std;
void doprime(bool *prime,int MAX)
{
long i,j;
memset(prime,true,MAX); //将prime中的所有元素赋为 true
prime[1]=false; //首先令第一个元为false，即1不为素数
for(i=2;i<MAX;i++) //从2开始，一直到最大值
{
if(prime[i]) //如果i为素数
{
for(j=i;j<MAX/i;j++)
{
prime[i*j]=false; //i的倍数全部都不是素数
}//end for
}//end if
}//end for
}//end doprime
int main(int argc, char *argv[])
{
bool a[101];
doprime(a,100);
for(int i=1;i<=100;i++)
求求哪位高手帮忙找找错！急用！
#include <cstdlib>
#include <iostream>
using namespace std;
void doprime(bool *prime,int MAX)
{
long i,j;
memset(prime,true,MAX); //将prime中的所有元素赋为 true
prime[1]=false; //首先令第一个元为false，即1不为素数
for(i=2;i<MAX;i++) //从2开始，一直到最大值
{
if(prime[i]) //如果i为素数
{
for(j=i;j<MAX/i;j++)
{
prime[i*j]=false; //i的倍数全部都不是素数
}//end for
}//end if
}//end for
}//end doprime
int main(int argc, char *argv[])
{
bool a[101];
doprime(a,100);
for(int i=1;i<=100;i++)
将for(j=i;j<MAX/i;j++) 改为for(j=i;j<=MAX/i;j++) 就OK了！！
其实就是一个界限的问题，如果只是j<MAX/i的话i*j的值就达不到99和100，自然prime[99]和prime[100]都不会被赋为false了！
楼主再算一下嘛,问题就在这!
问题出在筛的时候，内层j的循环：
for(j=i;j<MAX/i;j++)
你让j<MAX/i，是为了防止j溢出，但j，i，都是整型数，所以 i*（MAX/i）！=MAX,
如：MAX=100，i=2，MAX/2=50,j<50,所以100=2*50不会被筛掉，同理，99也不会被筛掉，
把for(j=i;j<MAX/i;j++)中的“<”改成“<=”就OK了^_^