素数判定
2019-01-11 08:33:53来源:博客园 阅读 ()
素数定义:质数定义为在大于1的自然数中,除了1和它本身以外不再有其他因数。
素数问题变化莫测,但万变不离其宗。素数问题最核心的就是如何判断一个数是否是素数。对于判断一个数m是否是素数,最原始的方法就是按照素数的定义,试除2开始到m-1的整数,如果无一例外地都不能整除,则该数一定是素数。实现程序如下:
using namespace std;
cin >> m;
for (int i = 2; i < m; ++i)
cout << m << " isn't a prime\n";
return 1;
}
cout << m << " is a prime\n";
return 0;
}
using namespace std;
int m;
cin >> m;
double sqrtm = sqrt(m*1.0);
for (int i = 2; i < sqrtm; ++i)
if (m%i == 0) {
cout << m << " isn't a prime\n";
return 1;
}
cout << m << " is a prime\n";
return 0;
}
using namespace std;
cout << "please inpout a number.";
int m;
cin >> m;
if (m == 2 || m == 3)
return 1;
double sqrtm = sqrt(m*1.0);
for (int i = 5; i <= sqrtm; i += 6)
if (m %i == 0 || m % (i + 2) == 0)
cout << m << " isn't a prime\n";
cout << m << " is a prime\n";
return 0;
}
using namespace std;
cout << "please inpout a number.";
int m;
cin >> m;
//两个较小数另外处理
if (m == 2 || m == 3)
return 1;
//不在6的倍数两侧的一定不是质数
if (m % 6 != 1 && m % 6 != 5) {
cout << m << " isn't a prime\n";
return 0;
}
double sqrtm = sqrt(m*1.0);
//在6的倍数两侧的也可能不是质数
for (int i = 5; i <= sqrtm; i += 6)
if (m %i == 0 || m % (i + 2) == 0)
cout << m << " isn't a prime\n";
//排除所有,剩余的是质数
cout << m << " is a prime\n";
return 0;
}
#include <ctime>
using namespace std;
int isPrime_2(int num);
int isPrime_3(int num);
int isPrime_4(int num);
int num = 30000;
int tstart, tstop; //分别记录起始和结束时间
tstart = clock();
for (int i = 1; i <= num; i++)
isPrime_1(i);
tstop = clock();
cout << "isPrime_1方法的时间(ms):" << tstop - tstart << endl;
tstart = clock();
for (int i = 1; i <= num; i++)
isPrime_2(i);
tstop = clock();
cout << "isPrime_2方法的时间(ms):" << tstop - tstart << endl;
tstart = clock();
for (int i = 1; i <= num; i++)
isPrime_3(i);
tstop = clock();
cout << "isPrime_3方法的时间(ms):" << tstop - tstart << endl;
tstart = clock();
for (int i = 1; i <= num; i++)
isPrime_4(i);
tstop = clock();
cout << "isPrime_4方法的时间(ms):" << tstop - tstart << endl;
return 0;
}
for (int i = 2; i <= num - 1; i++)
if (num %i == 0)
return 0;
return 1;
}
double sqrtnum = sqrt(num*1.0);
for (int i = 2; i <= sqrtnum; i++)
if (num %i == 0)
return 0;
return 1;
}
//两个较小数另外处理
if (num == 2 || num == 3)
return 1;
for (int i = 5; i <= sqrtnum; i += 6)
if (num %i == 0 || num % (i + 2) == 0)
return 0;
return 1;
}
//两个较小数另外处理
if (num == 2 || num == 3)
return 1;
//不在6的倍数两侧的一定不是质数
if (num % 6 != 1 && num % 6 != 5)
return 0;
double sqrtnum = sqrt(num*1.0);
//在6的倍数两侧的也可能不是质数
for (int i = 5; i <= sqrtnum; i += 6)
if (num %i == 0 || num % (i + 2) == 0)
return 0;
//排除所有,剩余的是质数
return 1;
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:反转整数
下一篇:剑指Offer整理笔记
- Prime Time UVA - 10200(精度处理,素数判定) 2019-08-16
- 简单的素数问题(C++) 2019-01-23
- PAT (Basic Level) Practice 1007 素数对猜想 2018-12-04
- 判断是不是素数 2018-12-04
- [算法]浅谈求n范围以内的质数(素数) 2018-11-28
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash