【算法】普通方法和筛选法求素数
2023-09-11 14:20:56 时间
素数指的是因子仅仅有1和本身的数(1不是素数),求解素数在数学上应用很广泛,而求解n以内的素数也是我们编程时常遇到的问题,在这个问题上,筛选法求解素数执行得很快。以下首先介绍怎样推断一个是不是素数,然后介绍用普通方法求n以内的素数,接着是筛选法求n以内的素数,最后是两种算法的执行时间比較
推断一个数是不是素数
算法思想:推断小于等于一个数的平方的全部大于1的整数是不是能整除这个数,假设能,则表明这个数不是素数;反之,则是素数。
//推断一个数是否为素数
bool isPlain(int value){
int m = sqrt(value);
if (value < 2) return false;
for (int i = 2; i <= m; i++){
if ((value%i)==0){
return false;
}
}
return true;
}
普通方法求解n以内的素数
算法思想:声明一个n大小的bool数组。初始值为false,然后从2開始推断一个数是否为素数。若是。则将其的布尔值定为true
//普通法求素数
bool* putong(int n){
bool* value = new bool[n];
for (int i = 0; i < n; i++)
value[i] = false;
for (int i = 2; i < n; i++){
if (isPlain(i)){
value[i] = true;
}
}
return value;
}
筛选法求n以内的素数
算法思想:找出小于等于n的开方的素数。然后将n内全部这些素数的倍数统统去掉,剩下的数就都是素数,也是通过布尔数组实现
//筛选法求素数
bool* shuaixuan(int n){
bool* value = new bool[n];
for (int i = 0; i<n; i++)
value[i] = true;
value[0] = false;
value[1] = false;
for (int i = 2; i <= sqrt(n); i++){
if (value[i] && isPlain(i)){
int c = 2;
int j = i*c;
while (j < n){
value[j] = false;
j = i*c++;
}
}
}
return value;
}
完整代码及执行结果
下述代码分别调用了普通方法和筛选法,可循环输入n(按Ctrl + C结束),以供不同数据的測试,后面附了一张执行測试的结果图
#include <iostream>
using namespace std;
#include <ctime>
#include <math.h>
#include <conio.h>
//推断一个数是否为素数
bool isPlain(int value){
int m = sqrt(value);
if (value < 2) return false;
for (int i = 2; i <= m; i++){
if ((value%i)==0){
return false;
}
}
return true;
}
//普通法求素数
bool* putong(int n){
bool* value = new bool[n];
for (int i = 0; i < n; i++)
value[i] = false;
for (int i = 2; i < n; i++){
if (isPlain(i)){
value[i] = true;
}
}
return value;
}
//筛选法求素数
bool* shuaixuan(int n){
bool* value = new bool[n];
for (int i = 0; i<n; i++)
value[i] = true;
value[0] = false;
value[1] = false;
for (int i = 2; i <= sqrt(n); i++){
if (value[i] && isPlain(i)){
int c = 2;
int j = i*c;
while (j < n){
value[j] = false;
j = i*c++;
}
}
}
return value;
}
int main(){
int n;
while (cin >> n){
int start = clock();
bool* value1 = putong(n);
int end = clock();
cout << "普通方法:" << end - start << endl;
start = clock();
bool* value2 = shuaixuan(n);
end = clock();
cout << "筛选法:" << end - start << endl;
delete[] value1;
value1 = NULL;
delete[] value2;
value2 = NULL;
}
_getch();
}
从图中可看出,n越大。筛选法对普通方法的性能就越好。
相关文章
- 机器学习流程,常规算法,降维方法
- python 模块 chardet下载方法及介绍
- 通过jdb命令连接远程调试的方法
- 【算法】【二叉树模块】二叉树的序列化和反序列化方法
- ArcGis 统计方法
- 基于凸优化的动态频谱分配算法matlab仿真,凸优化采用CVX工具箱,介绍CVX工具箱的使用方法。
- 基于PVO(Pixel-Value-Ordering)算法的高质量可逆隐藏方法和图像局部粗糙度分析
- 用形态学的方法实现图像的角点检测的算法原理详解和代码实现(Pyton和C++代码)
- C#,码海拾贝(19)——一般实矩阵的QR分解(QR Decomposition)方法之C#源代码,《C#数值计算算法编程》源代码升级改进版
- C#,码海拾贝(15)——“对称正定矩阵”的求逆和“托伯利兹矩阵”求逆的“埃兰特”方法之C#源代码,《C#数值计算算法编程》源代码升级改进版
- 《软件工程方法与实践》—— 1.5 软件工程开发方法学
- 《异构信息网络挖掘: 原理和方法》—— 2.2 RankClus算法
- JVM-对象内存回收方法与垃圾收集器算法
- Python 私有属性和私有方法
- 写一个针对IQueryable<T>的扩展方法支持动态排序
- numba算法库的介绍和使用方法
- 【APP渗透测试】Android APK常用测试工具(Drozer)安装及使用方法介绍
- linux安装字体方法
- 《Python机器学习——预测分析核心算法》——1.3 什么是集成方法
- 再探 游戏 《 2048 》 —— AI方法—— 缘起、缘灭(7) —— Python版本实现的《2048》游戏的TDL算法
- ArrayList输出的几种方法
- 【算法刷题】栈与队列题型及方法归纳
- 【算法刷题】哈希表题型及方法归纳
- 【机器学习算法-python实现】协同过滤(cf)的三种方法实现
- 给字符数组赋值的方法