数学知识-质数

简介: 数学知识-质数

文章目录



一、质数

227.png

二、质数的判定——试除法


题目描述


给定 n 个正整数 a i 判定每个数是否是质数。


输入格式


第一行包含整数 n。

接下来 n 行,每行包含一个正整数 a i


输出格式


共 n 行,其中第 i 行输出第 i 个正整数 a i

 是否为质数,是则输出 Yes,否则输出 No。


数据范围

228.png

具体实现

1. 实现思路

229.png


2. 实现代码

#include <bits/stdc++.h>
using namespace std;
bool is_prime(int x)
{
    //判断这个数是否大于等于 2 
    if (x < 2)
    {
        return false;
    }
    //判断是否还有别的约束
    for (int i = 2; i <= x / i; i ++ )
    {
        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;
}


三、分解质因数——试除法

题目描述

230.png


输入样例

2

6

8

输出样例

2 1

3 1

(空行)

2 3

(空行)


具体实现

1. 实现思路


我们需要注意的是,质因数的底数必须是质数。

暴力写法:从小到大枚举 n nn 的所有质因数,如果 n nn 模 i ii 等于 0 00,就求出 i ii 的次数即可。


void divide(int x)
{
    for (int i = 2; i <= x; i ++ )
    {
        if (x % i == 0) //i一定是质数
        {
            int s = 0;
            while (x % i == 0) 
            {
                x /= i;
                s ++ ;
            }
            cout << i << ' ' << s << endl;
        }
    }
}


233.png

2. 实现代码

#include <bits/stdc++.h>
using namespace std;
void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
    {
        if (x % i == 0) //i一定是质数
        {
            int s = 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;
    cin >> n;
    while (n -- )
    {
        int x;
        cin >> x;
        divide(x);
    }
    return 0;
}


四、筛质数


题目描述


给定一个正整数 n,请你求出 1 ∼ n  中质数的个数。


输入格式


共一行,包含整数 n 。


输出格式


共一行,包含一个整数,表示 1 ∼ n 中质数的个数。


数据范围

234.png


1. 朴素筛法

1.1 实现思路


  • 首先,我们将所有的数放入一个数组当中,然后从前往后观察,依次将每一个数的倍数删除掉。
  • 经过这样筛选过后,剩下的数就都是质数。

1.2 实现代码

#include <bits/stdc++.h>
using namespace std;
const int N= 1000010;
//cnt表示质数的个数
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i])
        {
            //跳出本次循环
            continue;
        }
        //primes[]数组存储质数
        primes[cnt ++ ] = i;
        //去除倍数
        for (int j = i + i; j <= n; j += i)
        {
            st[j] = true;
        }
    }
}
int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}


2. 线性筛法

2.1 实现思路

235.png

2.2 实现代码

#include <bits/stdc++.h>
using namespace std;
const int N= 1000010;
int primes[N], cnt;
bool st[N];
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i])
        {
            primes[cnt ++ ] = i;
        }
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0)  //primes[j]一定是i的最小质因子
            {
                break;
            }
        }
    }
}
int main()
{
    int n;
    cin >> n;
    get_primes(n);
    cout << cnt << endl;
    return 0;
}
















相关文章
|
7月前
|
人工智能 算法 BI
数学知识:质数与约数
数学知识:质数与约数
71 0
|
机器学习/深度学习 人工智能
数学问题之(矩阵快速幂)
数学问题之(矩阵快速幂)
数学问题之(矩阵加速递推快速幂)
数学问题之(矩阵加速递推快速幂)
数学知识-约数
数学知识-约数
|
算法 C++
算法基础系列第四章——数论之质数与约数(2)
算法基础系列第四章——数论之质数与约数(2)
124 0
算法基础系列第四章——数论之质数与约数(2)
|
机器学习/深度学习 算法 C++
算法基础系列第四章——数论之质数与约数(1)
算法基础系列第四章——数论之质数与约数(1)
188 0
算法基础系列第四章——数论之质数与约数(1)
|
算法
数学知识:质数(一)
复习acwing算法基础课的内容,本篇为讲解数学知识:质数,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
155 0
数学知识:质数(一)
|
算法 C++
数学知识:约数(一)
复习acwing算法基础课的内容,本篇为讲解数学知识:约数,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
137 0
数学知识:约数(一)
数学知识:约数(二)
AcWing 871. 约数之和
94 0
数学知识:约数(二)