C语言找素数的几种方法

2024-05-24 07:20| 来源: 网络整理| 查看: 265

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

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

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

void FindPrime() { int i = 0; int j = 0; for (i = 1; i 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 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 if (prime[i - 1])//如果是素数就筛选，不是就没有意义了 { for (int j = 2; i * j if(prime[i]==1)//打印剩余没有被筛选的数 printf("%d ",i+1); } return 0; }

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

【本文地址】

公司简介

联系我们