查找C语言素数的最佳算法

尝试编写一个程序，查找2-> N之间的所有素数. 希望尽快实现. [问题分析]: 针对此问题有两种解决方案: 一种是使用“筛方法”，另一种是从2-> N进行查找以找到质数. 首先，我们简要介绍一下“筛分法”以找到2〜20的质数. 它的方法是首先对2〜20的数字进行排序: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20首先，取出数组中最小的数字，即2，然后判断2是质数，并删除后者2的所有倍数. 2 | 3 5 7 9 11 13 15 17 19下一个最小的数字是3，将其取出，然后删除3 2 3的倍数| 5 7 11 13 17 19等，直到最后. 使用sieve方法查找质数时，许多非质数会重复. 例如，如果数字为3×7×17×23，则在删除3的倍数时将被删除，而在删除7、17、23时也将被删除. 存在“线性筛分方法”，可以排列删除顺序，以便每个非素数仅删除一次.

以提高效率. 因为“筛方法”不是我介绍的重点，所以我将不介绍它. 现在让我介绍第二种方法. 使用这种方法，首先想到的是从2到N逐一检查. 如果显示，则不显示，请检查下一个. 这是正确的方法，但是效率不高. 当然，2是质数，那么2的倍数不是质数. 如果让我从2变为N，则您已经测试了4，6，8 ...这些数字是不公平的？因此，第一个修改是仅测试2个和所有奇数. 同样，3是质数，但是6、9、12 ... 3的这些倍数不是. 因此，如果您可以跳过2和3的倍数而不进行测试，则任何6个连续数字将仅被测试2个. 以6n，6n + 1、6n + 2、6n + 3、6n + 4、6n + 5为例，6n，6n + 2、6n + 4是偶数，而6n + 3是3的倍数，所以如果2和3的倍数被忽略，只要测试的数字仅为6n + 1和6n + 5，那么工作量仅为先前构想的2/6 = 1/3，则此方法应用于编程. 还有另一个问题，即是否判断数字i是否为质数.

根据质数的定义，即仅1可以自己除，因此2〜i-1可以用于除i. 如果不进行除法运算，则我是质数. 观点是正确的，但与前一个观点一样笨拙. 当i> 2时，哪个数字可以除以i-1？没有为什么？如果i不是素数，则i = a×b，其中a和b都不是i也不是1；仅仅因为a> 1，a至少为2，所以b最多为i / 2，并且i的个数不需要去除2〜i-1，而2〜i / 2就足够了. 不仅如此，因为i = a×b，所以a和b不能大于sqrt（i），为什么呢？如果a> sqrt（i），b> sqrt（i），则a×b> sqrt（i）* sqrt（i）= i，因此我无法除以i. 如果i不是素数，则其最大因子为sqrt（i）；换句话说，使用2〜sqrt（i）进行测试. 但是，使用2〜sqrt（i）进行测试也很浪费. 就像以前一样，2取之不尽，用之不竭，所以2的倍数也取之不尽. 同样，3取之不尽，用之不竭，3的倍数也取之不尽...最理想的方法是将i除以质数.

但问题是这些质数从何而来？这是相对简单的，您可以准备一个数组prime []，用于存储找到的质数，它最初有2、3、5. 进行检查时，只需使用prime []中小于sqrt（i）的数字除以i . 如果不进行除法运算，则我是素数wintc求1—n所有奇数的和程序，将其放在prime []中，因此prime []中的素数会越来越多，直到满足该数量为止！不妨使用此描述来编写此程序，但是在编程时有两个小问题: 1.如果仅检查6n + 1和6n + 5？不难发现它们的距离是4、2、4、2.... 因此，您可以首先定义变量gab = 4，然后定义gab = 6-gab； 2.您不能使用sqrt（i）进行比较，因为它不精确. 例如，i = 121，在数学中，sqrt（i）自然是11，但是在计算机中的结果可能是10.9999999，因此删除的数字是2、3、5、7，并且不包含11，因此121是成为质数. 解决这个问题的方法非常简单. 代替平方根，使用平方. 例如，如果p * p <= i，则p用于除以i. 而且它的效率高于处方. [程序列表]: #include int creat_prime（int prime []，int n，int total）{注册int i;注册int j;注册int gab = 2;注册int count; for（i = 7 ; i <= n; i + = gab）{count = 1; gab = 6-gab; for（j = 0; prime [j] * prime [j] <= i; j ++）{if（i％prime [j ] == 0）{count = 0; break;}} if（count）{prime [total] = i; total ++;}}返回总计；} int main（void）{int prime [30000] = {2,3 ，5）; int total = 3; //找到素数int i; int n = 200000; //要查找的范围（> = 6）total = creat_prime（prime，n，total）; for（i = 0; i

您会发现会有很多时间要输出. 让我给您一个小提示，假设您编译的可执行文件是prime.exe，并且目录位于D: \中. 然后，在命令行上输入D: \，然后输入命令prime> 1.txt，以便将结果保存到1.txt. 您会发现，在int越过边界的前提下，它几乎马上就完成了！当然，该程序仍有改进的空间. 如果您有更好的建议，请与我联系. redraiment@126.com#include“ stdio.h” #include“ conio.h” main（）{int m，n，i，num; int p [100];长s; s = 2; m = 1; n = 1; num = 1; p [1] = 2;为（; num <100; num ++）; {对于（i = 1，m = 2 ;;）{m = p [i];如果（m> s / 2）中断；否则if（m * n s）i ++;} printf（“ p％d =％ld”，num，s）; s ++; } getch（）;}我自己写的，感觉没有问题. 运行结果始终是: p100 = 2令人沮丧~~~添加的问题: 哦~~提醒wintc疯狂〜这是真的吗？我用p [i]表示第i个质数似乎有这样的问题吗？ ？有什么帮助吗？可以实现类似的定义吗？ ？ ？最好的答案就是保存！保存！您的想法很好，也就是说，在编程时这个想法不清楚，也没有进行全面的考虑.

这是修改后的代码#include“ stdio.h” #include“ conio.h” main（）{int m，n，i，num; int p [100];长s; s = 2; m = 1; n = 1; num = 1; p [1] = 2; for（; num <100; num ++）/ *分号应为您的笔误O（∩_∩）O * / {for（i = 1，n = 2 ;;）/ *这里n = 2而不是m也是笔误吗？ * / {m = p [i];如果（m> s / 2）中断；否则if（m * n s）{i ++; n = 2;} / *在这里，想一想在尝试一个新数字或尝试一个新质数时，请仔细考虑，是的，您是否要初始化count变量？ * / / *在编程时不要将其视为理所当然，而是要考虑所有因素，是否已正确处理每个变量* /} p [num] = s; / *如果要使用质数表，该如何不记录素数表^ o ^ * / printf（“ p％d =％ld \ n”，num，s）; s ++;} getch（）;}使用质数表对您的程序有好处，但您的程序尚未发挥出最高的效能. 存在一些无用的判断和分配wintc求1—n所有奇数的和程序，并且不使用mod操作，这使程序复杂且效率低下. 我认为最好使用标准素数算法，它无处不在，不用讨论

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-254082-1.html