如何快速制作质数表 |
您所在的位置：网站首页 › 100000000以内的质数表 › 如何快速制作质数表 |
|
众所周知，素数指的是只能被1以及自身整除的大于1的数。而质数的应用非常广泛，那么如何能快速制作一张质数表(质数表指从2~n所有质数组成的表)呢？ 方法一： 开辟一个很长的bool类型数组（2~n），将其最小数i默认为质数，并将i出队列，然后删除所有i的倍数，反复以上过程可以得到一个从2开始到n之间所有的质数队列。 以上方法为欧几里得筛法，时间复杂度O（nlogn），空间复杂度O（n） 详情：欧几里德算法复杂度分析_jmhIcoding-CSDN博客_欧几里得算法复杂度 #include #include #define ll long long #define endl '\n' using namespace std; const unsigned ll maxnum = unsigned short(-1); //maxnum = 65535 const unsigned ll n = 1000000; // bool B[n]; //从2到n的数组默认为false:0(删除为1) ll A[maxnum]; //定义质数表 int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); clock_t start, end; start = clock(); //计数器num,用于计数当前质数的数组下标 ll num = 0; for (int i = 2; i < 10000000; ++i) { if (B[i]);//B[i]为真,B[i]非质数,该值被删除 else { //B[i]为假,B[i]为质数,将其所有倍数删除 A[num++] = i; for (int j = i |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |