记录一下我知道的找素数的方法，这里就拿生成1-100的素数表作例子来展示。

方法试除法试除开平方法辗转相除法更相相减法埃式筛选法

试除法

试除法就是把每一个数都拿它之前的所有数来除一遍，如果出现余数为0，则证明不是素数。 例如：要验证99是否为素数，就拿1-98来给99除。当除到3时发现余数是0，所以99不是素数

void FindPrime()

{

int i = 0; int j = 0;

for (i = 1; i <= 100; i++)//这里可以直接+=2，因为偶数不可能是素数

{

for ( j = 2; j <= i; j++)

{

if (i % j == 0)//如果余数为0，则不是素数，结束循环

break;

}

if(i==j)//如果j一直加到和i相等，证明i是素数

printf("%d ", i);

}

}

int main()

{

FindPrime();

}

试除开平方法

一个非素数可以拆成两个数相乘，这两个数的其中一个一定小于等于这个非素数的开平方 例如：20可以拆成4×5，4是小于等于根号20的。 如果出现了这两个数有其中一个大于该数的开平方，证明该数是素数 例如：19只能拆成1和19，19是大于根号19的。 减少了循环的次数，比试除法好一点。

void FindPrime()

{

int i = 0; int j = 0;

for (i = 1; i <= 100; i++)//这里可以直接+=2，因为偶数不可能是素数

{

for ( j = 2; j <= sqrt(i); j++)//判断在根号i之前是否有可以除整的数，有就不是素数

{

if (i % j == 0)//如果余数为0，则不是素数，结束循环

break;

}

if(j>sqrt(i)&&i!=1)//sqrt返回的是double类型，i如果是素数，j一定会比sqrt（i）大

printf("%d ", i);

}

}

int main()

{

FindPrime();

}

埃式筛选

埃式筛选是一种算素数的方法 举个例子来理解：2是素数，现在就要把2的倍数全部排除在外，则4，6，8…，100都被排除了。3也是素数，则6,9,12,…99被排除了，最后把没有被排除的数打印出来即可。 埃式筛选要用到bool类型，如果是素数就赋值1，不是就赋值0.由于原生C语言没有bool类型（C99引入了），我这里就用数组来做。

int main()

{

int prime[1000] = { 0 };

for (int i = 0; i < 1000; i++)

{

prime[i] = 1;//假设全部数都是素数，全部赋值为1

}

for (int i = 2; i < 1000; i++)//第一个素数2开始筛选

{

if (prime[i - 1])//如果是素数就筛选，不是就没有意义了

{

for (int j = 2; i * j <= 1000; j++)//把2的倍数都筛选掉

{

prime[i * j - 1] = 0;//赋值为0，则不是素数了

}

}

}

for (int i = 0; i < 1000; i++)

{

if(prime[i]==1)//打印剩余没有被筛选的数

printf("%d ",i+1);

}

return 0;

}

有不对的地方请指正。谢谢啦