锐客网

  1. 首页 > 睿知 > >

c 中求素数代码，C语言求素数的程序

睿知经验分享

1，C语言求素数的程序if(a < 2)printf("Input error,re-enter:\n ");scanf("%d", &a); }if改为while,因为if不是循环只能判断一次,刚才又检查了一下 ， 你prime有错误for(i=2; i<=a/2; i++)i < a/2,<改成<=
2，看一段C求素数的代码#include"stdio.h" #include"math.h" main()int i,a; for(i=101;i&lt;=200;i++)flag=1; for(a=2;a&lt;=sqrt(i);a++) } if(flag==1)printf("%d ",i); }} //每次都要重置flag 。
3，新手求c语言求素数啊if(i=x-1) 改为 if(i==x-1) 你写的是赋值运算，是初学者经常犯的错误 。网上的代码意思是：n就是你输入的任意数，判断它是否是素数的方法是用大于2小于n的数去除n ， 若能整除即不是素数，跳出循环；若数一直增加到n+1都没有被整除，即可输出“素数” 。你的源程序：3是素数 ， 很简单，所以用if来提醒输入大于3的数 ， 你的只是另一种素数算法，是优化的算法，更快 。因为只需用2到根号a去判断 。【c 中求素数代码，C语言求素数的程序】
4，c程序求素数#include &lt;stdio.h&gt;#include &lt;math.h&gt;int f(int n) //起到判断大于1的正整数是否为素数的作用 ， 返回一个值以标识，是则返回1，否则返回0 。int i; for(i=2;i&lt;=sqrt(n);i++) if(n%i==0) return 0; return 1;}int main() printf("100至300之间的素数从小到大分别为:\n"); int i,k=0; for(i=100;i&lt;=300;i++) if(f(i))k++; printf("%d\t",i); //符号“\t”的作用是横向制表 。} printf("\n总共%d个 。\n",k ); return 0;}5，c程序求素数#include #include int f(int n) //起到判断大于1的正整数是否为素数的作用，返回一个值以标识，是则返回1，否则返回0 。{ int i; for(i=2;i<=sqrt(n);i++) if(n%i==0) return 0; return 1; } int main() { printf("100至300之间的素数从小到大分别为:\n"); int i,k=0; for(i=100;i<=300;i++) if(f(i)) { k++; printf("%d\t",i); //符号“\t”的作用是横向制表 。} printf("\n总共%d个 。\n",k ); return 0; }#include "stdio.h"void main() int n = 0,w = 1,i = 2; scanf("%d",&amp;n); while(i &lt;= (n-1) &amp;&amp; w == 1) if(n%i == 0) w = 0; }else i = i+1; } } if(w == 1) printf("%d是素数\n",n); }else printf("%d不是素数\n",n); } }这个程序有很多地方被我改了 。呵呵，其实你写的那个程序主要的问题就是赋值号与等号的写法 。其他地方没什么问题，你可以自己改你的原程序试试 。授之以鱼不如授之以渔：思想：【1】求10000以内的所有素数 。素数是除了1和它本身之外再不能被其他数整除的自然数 。由于找不到一个通项公式来表示所有的素数，所以对于数学家来说，素数一直是一个未解之谜 。像著名的 哥德巴赫猜想、孪生素数猜想，几百年来不知吸引了世界上多少优秀的数学家 。尽管他们苦心钻研 ， 呕心沥血，但至今仍然未见分晓 。自从有了计算机之后，人们借助于计算机的威力，已经找到了2216091以内的所有素数 。求素数的方法有很多种，最简单的方法是根据素数的定义来求 。对于一个自然数N，用大于1小于N的各个自然数都去除一下N，如果都除不?。騈为素数，否则N为合数 。但是，如果用素数定义的方法来编制计算机程序，它的效率一定是非常低的，其中有许多地方都值得改进 。第一，对于一个自然数N，只要能被一个非1非自身的数整除 ， 它就肯定不是素数，所以不必再用其他的数去除 。第二 ， 对于N来说，只需用小于N的素数去除就可以了 。例如 ， 如果N能被15整除，实际上就能被3和5整除 ， 如果N不能被3和5整除，那么N也决不会被15整除 。第三，对于N来说，不必用从2到N一1的所有素数去除，只需用小于等于√N(根号N)的所有素数去除就可以了 。这一点可以用反证法来证明：如果N是合数，则一定存在大于1小于N的整数d1和d2，使得N=d1×d2 。如果d1和d2均大于√N，则有：N＝d1×d2>√N×√N＝N 。而这是不可能的，所以，d1和d2中必有一个小于或等于√N 。基于上述分析，设计算法如下：(1)用2 ， 3，5，7逐个试除N的方法求出100以内的所有素数 。(2)用100以内的所有素数逐个试除的方法求出10000以内的素数 。首先，将2，3，5，7分别存放在a[1]、a[2]、a[3]、a[4]中，以后每求出一个素数，只要不大于100 ， 就依次存放在A数组中的一个单元 中 。当我们求100—10000之间的素数时，可依次用a[1]－a[2]的素数去试除N ， 这个范围内的素数可以不保存，直接打印 。【2】用筛法求素数 。简单介绍一下厄拉多塞筛法 。厄拉多塞是一位古希腊数学家，他在寻找素数时，采用了一种与众不同的方法：先将2－N的各数写在纸上：在2的上面画一个圆圈，然后划去2的其他倍数；第一个既未画圈又没有被划去的数是3，将它画圈 ， 再划去3的其他倍数；现在既未画圈又没有被划去的第一个数 是5，将它画圈，并划去5的其他倍数……依次类推，一直到所有小于或等于N的各数都画了圈或划去为止 。这时，表中画了圈的以及未划去的那些数正好就是小于 N的素数 。这很像一面筛子，把满足条件的数留下来，把不满足条件的数筛掉 。由于这种方法是厄拉多塞首先发明的，所以 ， 后人就把这种方法称作厄拉多塞筛法 。在计算机中，筛法可以用给数组单元置零的方法来实现 。具体来说就是：首先开一个数组：a[i] ， i=1，2 ， 3，…，同时，令所有的数组元素都等于下标 值，即a[i]=i，当i不是素数时，令a[i]=0。当输出结果时 ， 只要判断a[i]是否等于零即可，如果a[i]=0 ， 则令i=i+1，检查下一个a[i] 。筛法是计算机程序设计中常用的算法之一 。【3】用6N±1法求素数 。任何一个自然数 ， 总可以表示成为如下的形式之一：6N，6N+1 ， 6N+2，6N+3，6N+4，6N+5 (N=0，1 ， 2，…)显然，当N≥1时，6N，6N+2，6N+3 ， 6N+4都不是素数，只有形如6N+1和6N+5的自然数有可能是素数 。所以，除了2和3之外，所有的素数都可以表示成6N±1的形式(N为自然数) 。根据上述分析 ， 我们可以构造另一面筛子，只对形如6 N±1的自然数进行筛选 ， 这样就可以大大减少筛选的次数，从而进一步提高程序的运行效率和速度 。在程序上，我们可以用一个二重循环实现这一点 ， 外循环i按6的倍数递增，内循环j为-1和1的循环，则i+j恰好就是形如6N±1的自然数 。

    推荐阅读


    上一篇：各种编程语言的特点和作用，谁能告诉我每个编程语言的特点及作用

    下一篇：冬季中老年人谨防脑卒中