算法练习专栏——埃氏筛法+约数个数+约数和

一、筛质数（简单+）

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

输入格式

共一行，包含整数 n。

输出格式

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

数据范围

$$
\begin{flalign}
&1≤n≤10^6&
\end{flalign}
$$

输入样例：

1
8

输出样例：

1
4

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
using namespace std;
const int N = 1e6 + 10;

int n,cnt,primes[N];
bool st[N];

int prime(int x)
{
    for (int i = 2; i <= n;i ++)
    {
        if (!st[i]) 
        {
            primes[cnt++] = i;
            for(int j = i + i; j <= n; j = j + i) st[j] = true;
        }
    }
    return cnt;
}
int main()
{
    cin >> n;
    
    cout << prime(n);
    
    return 0;
}

二、约数个数(简单+)

给定 n 个正整数 ai，请你输出这些数的乘积的约数个数，答案对 10^9^+7 取模。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数 ai。

输出格式

输出一个整数，表示所给正整数的乘积的约数个数，答案需对 10^9^+7 取模。

数据范围

1≤n≤100
1≤ai≤2×10^9^

输入样例：

1
2
3
4
3
2
6
8

输出样例：

1
12

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstring>
#include <unordered_map>

using namespace std;
const int mod = 1e9 + 7;
int n;


int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    unordered_map<int, int> prime;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        for (int i = 2; i * i <= x; i ++) {
            while (x % i == 0) {
                x /= i;
                prime[i]++;
            }
        }
        if (x > 1) prime[x]++;
    }

    long long res = 1;
    for (auto k:prime) {
        res = res * (k.second + 1) % mod;
    }
    
    cout << res;
    return 0;
}

三、约数的和

给定 n 个正整数 ai，请你输出这些数的乘积的约数之和，答案对 10^9^+7取模。

输入格式

第一行包含整数 n。

接下来 n 行，每行包含一个整数 ai。

输出格式

输出一个整数，表示所给正整数的乘积的约数之和，答案需对 10^9^+7取模。

数据范围

1≤n≤100
1≤ai≤2×10^9^

输入样例：

1
2
3
4
3
2
6
8

输出样例：

1
252

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
#include <unordered_map>

using namespace std;
const int mod = 1e9 + 7;
int n;


int main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    unordered_map<int, int> prime;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        for (int i = 2; i * i <= x; i ++) {
            while (x % i == 0) {
                x /= i;
                prime[i]++;
            }
        }
        if (x > 1) prime[x]++;
    }

    long long res = 1;
    for (auto k:prime) {
        int a = k.first, b = k.second;
        long long tt = 1;
        for (int i = 0; i < b; i++) {
            tt = (tt * a + 1) % mod;
        }
        res = res * tt % mod;
    }
    
    cout << res;
    return 0;
}