首页 > 代码库 > 素数的判断
素数的判断
一、朴素判定
bool isPrime(int n) { if (n == 1) { return false; } for (int i = 2; i * i <= n; ++ i) { if (n % i == 0) { return false; } } return true; }
二、欧拉筛判断素数
1 int isPrime[maxn]; 2 void getPrime(int n) { 3 memset(isPrime, 1, sizeof(isPrime)); 4 for (int i=2;i<=n;++i) { 5 if (!isPrime[i]) continue;//已经不是素数的数其n(n>1)倍也不是素数 6 for (int j=i*2;j<=n;j+=i) { 7 isPrime[j]=false; 8 }//一个数的n倍一定不是素数(n>1) 9 }//把所有不是素数的数字标记 10 }
三、线性筛判断素数
/*原理: 1. 任何一个合数都可以表示成一个质数和一个数的乘积 2. 假设A是一个合数,且A = x * y,这里x也是一个合数,那么有: A = x * y; (假设y是质数,x合数) x = a * b; (假设a是质数,且a < x——>>a<y) -> A = a * b * y = a * Z (Z = b * y) 即一个合数(x)与一个质数(y)的乘积可以表示成一个更大的合数(Z)与一个更小的质数(a)的乘积! 理解if(i%prime[ j ]==0)是关键。 */ int isPrime[maxn];//相当于判断该数字是不是质数的bool变量 int totprime, primes[maxn];//tot表素数个数和,primes盛质数 void getPrime(int n) { memset(isPrime, 1, sizeof(isPrime)); totprime=0; for (int i=2;i<=n;++i) { if (isPrime[i]) { primes[totprime ++]=i; } for (int j=0,k;j<totprime&&i*primes[j]<=n;++j){ k=i*primes[j]; isPrime[k]=false; if (i%primes[j]==0) { break; } } } }
四、1-n所有约数的和
#include <iostream> using namespace std; int main() { int n; long long ans=0; cin>>n; for (int i=1;i<=n;++i) { ans+=(long long)i*(n/i); } cout<<ans<<endl; }
素数的判断
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。