判断n是否为素数的最快方法 除了从2开始递增到n的平方根之外 还有什么方法么
因为如果一个数不是素数是合数， 那么一定可以由两个自然数相乘得到， 其中一个大于或等于它的平方根，一个小于或等于它的平方根。并且成对出现。 程序改了下： #include int main(void) { int m,i; scanf("%d",&m); for(i=2;i<m;i++) { if(m%i==0) break; } if (i < m) printf("%d is not a prime number
",m); else printf("%d is a prime number
",m); return 0; }
判断一个数是否素数，只需判断它是否有非1，非本身的正因子。
一般算法都是从2开始判断，设该数是N，假如N有大于 根号N 的因子，那么它的另一个因子必小于 根号N，那么计算机运算时查到这个因子时就可判断它不是素数，因此只需到平方根，而不必查到 N-1
除此之外还有一个概率的方法。
如果是频繁判素数的话，建议先素数打表。
如果不是太要求效率的话，楼主的方法够了。
急求!! 判断用户输入的正整数n是否为素数(n<1000),直到用户输入1为止...
include <iostream> include <math.h> using namespace std;int main(void){ int n=0;\/\/用户输入 int i=0;\/\/for循环用 bool flag=false;\/\/判断是否为素数 int inputNum(void);\/\/用以输入一个正整数 n=inputNum();\/\/输入数据 while( n!=1 ){ flag=true;for(i=2;i<=sqrt((float)...
c语言怎么判断一个数是不是素数?
遍历2到100之间所有整数，然后逐一判断是否为素数，如果是则存入数组。最终遍历数组输出每个值即可。 具体如下：1、素数的判断。根据素数定义，除了1和本身不存在其它约数的正整数为素数。所以在C语言中判断n是否为素数可以从2开始到到n-1逐一尝试，如果可以整除说明不是素数。更进一步，可以从2判断到n\/...
c语言 判断素数 程序不太明白
素数即只能被1和其本身整除的数，判断n是否为素数只需用2~n\/2或2~之间的数去除就可以了，常用2~n\/2，因为一个数的一半的平方大于其本身是从5开始的 一个数n的两个因数不能同时比n\/2大。就可以说一个数若不是素数则一定在2~n\/2之间有因数。for(i=2;i<=m\/2;i++) 就是判断 2-n\/2...
如何判断一个数是不是素数
1、最直观的方法是逐个判断该数能否被小于它的数整除。从2开始，一直到该数的平方根，依次判断能否被这些数整除。如果能被整除，则不是素数；如果不能被整除，则是素数。2、利用数学性质，可以进一步优化判断素数的方法。如果一个数是合数，那么它必然存在非1的两个约数p1和p2，其中p1<=sqrt(n)，p2...
编写一个函数prim,要求判定正整数n是否为素数,调用上述函数,按每行十...
1．首先编制一个函数prim，用于判断正整数n是否为素数。该函数的函数头部分为：int prim(int n)函数体部分：（1）定义2个变量，一个变量是用于循环计数用的变量，另一个变量（假设用flag）是用于作为判断n是否为素数的标记（初值为1，表示为素数）；（2）处理部分是一个循环结构，循环条件：初值为...
判断一个数是否为素数?
最直观的方法判断。根据定义，因为素数除了1和本身之外没有其他约数，所以判断n是否为素数，根据定义直接判断从2到n-1的数中有没有N的约数？如果找不到这样的约数，那么这个数就是素数，否则就不是素数。首先是看这个数是否是大于1的自然数，然后看它除了1和这个数字本身之外还有没有其他的因数，比如...
判断一个整数是否为素数
目前为止，人们未找到一个公式可求出所有质数。2016年1月，发现世界上迄今为止最大的质数，长达2233万位，如果用普通字号将它打印出来长度将超过65公里。质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大...
用c++判断一个数是否是素数
首先先定义一个函数用于判断一个数是否是素数，接着主函数接受键盘输入，并调用该函数判断输入的数是否是素数。素数就是只能被1和自身整除的数。故判断n是否是素数，可以用n依次除以n-1,n-2……2，如果能整除则不是素数，否则是素数。参考代码如下：include<stdio.h>#include<iostream>using namespace...
用VB编写一段代码判断输入的数是否素数。
3、双击表单以编写代码，单击设置过程，对象为表单form1。4、接着输入代码内容：代码的内容是根据题目定义的。5、单击“开始”按钮进行编译和调试，并根据错误提示修改它，直到它正确为止。6、单击表单将弹出一个提示对话框，输入值确定素数，单击确定按钮，此时自动判断并给出结果。7、执行文件 - 保存...
从键盘输入一个整数,判断它是否为素数
include"iostream.h"include"math.h"define N 1000 bool fun(int n){ int i;if(n<=2) return 1;for(i=2;i<=sqrt(n);i++)if(n%i==0) return 0;return 1;} void main(){ int n;cout<<"请输入你要判断的数n:"<<endl;cin>>n;if(fun(n))cout<<"n是素数!"<<endl;else c...
中叔宝复方：[答案] 如果n不是很大的话,这就够了. 除此之外还有一个概率的方法. 如果是频繁判素数的话,建议先素数打表. 如果不是太要求效率的话,楼主的方法够了.
下关区18892931132： 求判断一个数是否为素数的最简单算法一个数N,从实现最为简单的算法就是遍历N能否整除从2到sqrt(N).若不能则为素数.不过这个算法计算量挺大的 - ？
中叔宝复方：[答案] 追求效率的话 最高的是 Miller_Rabin 算法 最好有一定的数论知识再去看 另一个简单方法是 可以O(n) 求出素数 然后再判断就行了 多个素数判断时效率较高
下关区18892931132： 判定素数的方法有哪些?它们的时间复杂度分别是多少?(越详细越好, - ？
中叔宝复方：[答案] 几种简单的判断素数的方法素数还有很多东西需要学,先整理三种最简单的判断素数的方法,以后再深究补充.判断n是否为素数1、最简单的方法用n除以2-sqrt(n),有一个能除尽就不是素数,否则是素数.时间复杂度:O(sqrt(n))2...
下关区18892931132： 检查一个正整数N是否为素数,最简单的方法就是试除 - ？
中叔宝复方： 检查一个正整数N是否为素数,最简单的方法就是试除 设√N=A,(默认A非整数,若N=A平方,A为整数,则N不是素数),设小于A的最大素数为P,分别以2、3、5、7、11、...、P去除N,若都不能整除,则N是素数.
下关区18892931132： 如何证明埃拉托斯特尼筛法!检查一个正整数N是否为素数,最简单的方法就是试除法,将该数N用小于等于根号N的所有素数去试除,若均无法整除,则N为... - ？
中叔宝复方：[答案] 利用反证法:假设这样筛出来的N是合数,且不能被小于等于其平方根的所有素数整除,那么N一定能被大于其平方根小于其本身的某个素数整除.记该素数为M,则√N
下关区18892931132： 判断一个数是否为素数的算法判断一个数n是不是素数,我只知道有这个方法:让n除以2到n的平方根之间的每一个数,如果n能被2到n的平方根之间的某个... - ？
中叔宝复方：[答案] 因为没必要去比较大于n/2的情况,因为n=2*n/2,假设m>n/2,那么n必然不能被m整除,就好像100=2*50,不需要再去比较51,52....
下关区18892931132： 求一个数怎样判断它是不是素数 - ？
中叔宝复方： 用辗转相除法,思路是:采用循环将这个数N从2开始除,一直除到N-1为止,其间若发现除尽,则跳出循环,认为它不是素数,若一直无法除尽,则判定其为素数 .
下关区18892931132： 判断n是不是素数,只需被2~根号n之间的整数除? - ？
中叔宝复方： 如果一个数n是合数,则可写为n=p*q*……,项数越多则质因数整体越小. 设p为n的最小质因数,则2<=p<=sqrt(n). 用反证法,设p>sqrt(n),因为 n/p 也是 n 的因子(不一定是质因子),令q=n/p, 由假设p是n最小的质因子,而q 至少包含n的一个因子,故q>=p. 即 n=pq>=p*p>sqrt(n)*sqrt(n)=n, 此式矛盾,故假设不成立,即 p<=sqrt(n). 即合数n的最小质因子不大于sqrt(n),它的逆否命题就是: 如果数n在[2,sqrt(n)]之间没有质因子则n为质数
下关区18892931132： 怎样判断一个数n是质数(素数)还是和数 - ？
中叔宝复方： 根据质数的定义,在判断一个数n是否是质数时,只要用1至n-1去除n,看看能否整除即可. 还有更好的办法:先找一个数m,使m的平方大于n,再用小于等于m的质数去除n(n为被除数),如果都不能整除,则n必然是质数.如我们要判断1993是...
下关区18892931132： 为什么求素数n只要只要除到根号n就可以判断是否是素数了? ？
中叔宝复方： 如果n不是素数 n=a*b (n>a>1 n>b>1) 那么 a 和 b一定有一个不超过根号n [否则 n=a*b>(根号n)*(根号n)=n,矛盾] 于是只要除到根号n就可以判断是否是素数
