素数判定及筛的总结 |
您所在的位置：网站首页 › 1319是质数吗 › 素数判定及筛的总结 |
|
文章目录
概念性质常用的判断素数的方法:1.试除法2.取模法3.埃氏筛4.欧拉筛
待更新本文程序计时模板
本文只写了较常见的几种素数求法及筛法，实际上方法多种多样，但这些也已经足够用了(学不会其他的) 概念素数研究是数论中最古老、也是最基本的部分，素数即质数 定义为在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数 性质1.素数p的约数：1 和 p 2.唯一分解定理：任意大于 1 的自然数，要么本身是素数，要么可以分解为几个素数之积，且这种分解是唯一的 3.素数的个数是无限的 常用的判断素数的方法: 1.试除法在特判 0 1 2 后，再在区间 [2，n) 之间试图找出一个数能把 n 整除，若找到，则返回 0 ，说明 n 不是素数，若没找到，最终返回 1 ，说明 n 是素数 int f(int n){ if(n if (n == 1)return 0; if (n == 2 || n == 3)return 1; if (n % 6 != 5 && n % 6 != 1)return 0; int x=sqrt(n); for (int i = 5; i vis[0]=vis[1]=1;//0 1不是素数 for(int i=2;i vis[0] = vis[1] = 1;//0 1不是素数 int x = sqrt(N); for (int i = 2; i prime[cnt++]=i; for (int j = i * i; j if (!vis[i]) prime[cnt++] = i; //遍历已知素数表 for (int j = 0; j //clock_t为CPU时钟计时单元数 clock_t start, finish; //clock()函数返回此时CPU时钟计时单元数 start = clock(); //待测时的代码执行区： //...... //clock()函数返回此时CPU时钟计时单元数 finish = clock(); //finish与start的差值即为程序运行花费的CPU时钟单元数量，再除每秒CPU有多少个时钟单元，即为程序耗时 cout |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
| CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |