前言:
眼前你们对“c语言求素数因子”大体比较关注,朋友们都需要知道一些“c语言求素数因子”的相关资讯。那么小编在网摘上收集了一些关于“c语言求素数因子””的相关知识,希望小伙伴们能喜欢,大家一起来了解一下吧!想必大家在上学期间我们都编写过寻找某区间的素数,但是怎么能优化我的代码,怎么样能够写出漂亮的代码,这就需要我们来下功夫了。
素数:质数又称素数。一个大于1的自然数,除了1和它自身外,不能被其他自然数整除的数叫做质数;否则称为合数。
给出常用的简单的三种方法:遍历法(也可理解为穷举法)、折半法、开根法。
// vs_2.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <stdio.h>#include "math.h"//方法1:最简单方法(从2到n-1每个数均整除判断)时间复杂度O(n)int isPrime0(int k){ /*判断n是否是素数,是则返回1,不是则返回0*/ int j; for(j=2;j<k/2;j++){ if(k%j==0) return 0;/*n可以被i整除,因此n不是素数,返回0*/ } return 1;/*n是素数,返回1*/}//方法2:遍历到 k/2,就可以了,数学知识int isPrime1(int k){ /*判断n是否是素数,是则返回1,不是则返回0*/ int j; if (k <= 1) { printf("illegal input!\n");//素数定义 return -1; } for(j=2;j<k/2;j++){ if(k%j==0) return 0;/*n可以被i整除,因此n不是素数,返回0*/ } return 1;/*n是素数,返回1*/}//方法3:开根法,数学知识/* 从2到\sqrt{}n均整除判断,时间复杂度O(\sqrt{}n) (原因:素数是因子为1和本身, 如果数c不是素数,则还有其他因子, 其中的因子,假如为a,b.其中必有一个大于sqrt(c) ,一个小于sqrt(c) 。 所以m必有一个小于或等于其平方根的因数, 那么验证素数时就只需要验证到其平方根就可以了。 即一个合数一定含有小于它平方根的质因子。)*/int isPrime2(int k){ int i; if (k <= 1) { printf("illegal input!\n");//素数定义 return -1; } for(i=2;i<=(int) sqrt((double) k);i++){ if(k%i==0) return 0;/*n可以被i整除,因此n不是素数,返回0*/ } return 1;/*n是素数,返回1*/}void getPrime(int low,int high){ /*寻找[low,high]之间的素数*/ int i; if(low > high){ printf("error !\n");//素数定义 return ; } for(i=low;i<=high;i++) { if(isPrime2(i)) { printf("%d ",i); /*如果i是素数,则打印出来*/ } }}int main(int argc, char* argv[]){ int low,high; printf("Please input the domain for searching prime\n"); printf("low limitation:"); scanf("%d",&low); printf("high limitation:"); scanf("%d",&high); printf("The whole primes in this domain are\n"); getPrime(low,high); while(1){ } //getchar(); return 0;}
运行结果:执行效率非常的快。
版权声明:
本站文章均来自互联网搜集,如有侵犯您的权益,请联系我们删除,谢谢。
标签: #c语言求素数因子