c++ 质数_c++质数

这一篇的内容为质数，质数也被叫为素数，只能被一和被自身整除

下面开始第一个算法，关于判断是不是质数的办法

1、试除法：时间复杂度（0（sqrt（n）））

先直接给出代码，如下

#include <iostream>
#include <algorithm>
 
using namespace std;
 
bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )//这里用除法是防止爆int
        if (x % i == 0)
            return false;
    return true;
}
 
int main()
{
    int n;
    cin >> n;
 
    while (n -- )
    {
        int x;
        cin >> x;
        if (is_prime(x)) puts("Yes");
        else puts("No");
    }
 
    return 0;
}

为什么要用x/i,而不是用sqrt，是因为每次到这边判断的时候，就要调用一次关于sqrt的函数，这样的话如果计算的次数太多就会浪费太多时间，而且相除的话可以防止爆int

2、分解质因数

一个正整数肯定有质因数，因为1比较特殊，所以把1排除在外今天的讨论

今天要讨论的求出每个数分解之后的质因数，而且质因数是由小到大

比如8,8是2^3,2*2*2，所以8的质因数是2

比如12，是2*2*3

但如果一个数本声就是质数，那就是只有1和本身

求出每一个数的质因数的代码先给出如下

#include<iostream>
#include<algorithm>
 
using namespace std;
 
void divide(int x)
{
    for(int i=2;i<=x/i;i++)
    {
        int s=0;
        if(x%i==0)
        {
            while(x%i==0) x/=i,s++;
            cout<<i<<' '<<s<<endl;
        }
    }
    if(x>1) cout<<x<<' '<<1<<endl;
    cout<<endl;
}
 
int main()
{
    int n;
    scanf("%d",&n);
    
    while(n--)
    {
        int x;
        scanf("%d",&x);
        divide(x);
    }
    return 0;
}

先从2开始，判断2是不是能够整除，如果不能，再依次增大i的值

如果可以整除，那么再一直整除到不能整除i的时候，而且这个时候第一个i就是最小的质因数，之后再依次增大，但如果一直到x/i也没有结果，就跳出循环

但是从1到x中只有一个质因数大于x/i，所以就指数就输出1

3、筛质数

这个是给定一个正整数 nn，请求出 1∼n 中质数的个数

如果遇到这样的问题，再暴力做法，只要询问的次数太多就很可能超时，这个办法只能是询问次数很少的时候才可以用

埃氏筛法o(nsqrt(n))

从1到n中，一次剔除从2开始的倍数

比如从1到8中

2的倍数是4,6,8

3的倍数是6

4的倍数是8

这样的话会多次剔除，但也比暴力解法更快

代码如下

#include<iostream>
#include<algorithm>
 
using namespace std;
 
const int N=1000010;
 
int prime[N],cnt;
bool st[N];
 
void get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(st[i]) continue;
        prime[cnt++]=i;
        for(int j=i+i;j<=n;j+=i)
        {
            st[j]=true;
        }
    }
}
 
int main()
{
    int n;
    scanf("%d",&n);
    
    get_primes(n);
    
    cout<<cnt<<endl;
    
    return 0;
}

从2开始，如果不是质数的话，就一直continue,直至遇到质数，然后cnt求的就是次数，cnt++,同时把该质数弄到prim[N]中，下面一个循环就是从倍数开始剔除

线性筛法o(n)

线性筛法和埃氏筛法的一个很大的区别就是线性筛法每次只筛一次，而且剔除的是该质数和最小质因数的倍数

代码如下

#include<iostream>
#include<algorithm>
 
using namespace std;
 
const int N=1000010;
 
int prime[N],cnt;
int st[N];
 
int get_primes(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) prime[cnt++]=i;
        for(int j=0;prime[j]<=n/i;j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0) break;
        }
    }
}
 
int main()
{
    int n;
    cin>>n;
    
    get_primes(n);
    
    cout<<cnt<<endl;
    
    return 0;
}

最后希望大家来到acwing一起学习