开周边网站怎么做品牌,六盘水市诚信网站建设公司,鞍山制作网站的公司,宝安建网站公司素数的定义#xff1a;
首先我们明白#xff1a;素数的定义是只能整除1和本身#xff08;1不是素数#xff09;。
我们判断一个数n是不是素数时#xff0c;可以采用试除法#xff0c;即从i2开始#xff0c;一直让n去%i#xff0c;直到i*in
c语言:
#include…
素数的定义
首先我们明白素数的定义是只能整除1和本身1不是素数。
我们判断一个数n是不是素数时可以采用试除法即从i2开始一直让n去%i直到i*in
c语言:
#includestdio.h
int main()
{int n;for (int i 2; i * i n; i){if (n % i 0){printf(%d 不是素数,n);return 0;}}printf(%d 是素数, n);
}
C:
#includeiostream
using namespace std;
int main()
{int n;for (int i 2; i * i n; i){if (n % i 0){coutn不是素数;return 0;}}coutn是素数;
}
但是问题来了如果一两个数让你去判断你这么试除一下还行那要是一堆大且多的荒谬的数据让你去判断你需要循环的次数也是一个天文数字。这个时候我们就可以通过一些算法来实现对于大数据大且多素数的判断。 埃筛与欧拉筛的实质 其实埃筛与欧拉筛的实质都且就是围绕这一句话素数的倍数不是素数。
比如说让你输出100000——1e5内所有的素数
那我们就筛就好啦首先咱需要创建一个存素数的数组和一个bool类型的数组用来判断该元素是否是素数)
埃氏筛:
//埃氏筛法
int n1e5;
bool shai[n];
int cun[n];
signed main()
{int cnt 0;for (int i 2; i n; i){if (!shai[i])//如果为0{cun[cnt] i;for (int j 2; j n; j){if (i * j n)break;//超过数据大小就退掉。shai[i * j] 1;//1的都是素数的倍数——所以不是素数。}}}for (int i 0; i cnt; i){printf(%d , cun[i]);}
}
我们先看一看欧拉筛
欧拉筛
#includeiostream
using namespace std;
bool a[100001] { 1,1 };//同上问一样i0,i1的时候都不是质数
int b[100001];//存质数
long long n;
int main()
{int cnt 0;cin n;//查的范围for (int i 2; i n; i){if (a[i] 0) b[cnt] i;for (int j 1; j cnt; j){if (i * b[j] n)break;// 如果超出给出的范围那么就退出循环 a[i * b[j]] 1;//素数的倍数不是素数进行标记。if (i % b[j] 0)break;//超级关键的只标记一次}}for (int i 1; i cnt; i){printf(%d , b[i]);}
}
欧拉筛比埃筛要快很多很多
我们看看埃筛就从2开始它是素数所以内循环会标记4,6,8,10,12······一直到退出循环然后当外层循环到3的时候它又会标记6,9,12······在这里我们就能看出一点问题有数被重新标记了而且循环到后面重复标记的数量会很多,所以浪费了时间。
