跳转至

质数

例题

Prime Distance

 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
40
41
42
43
44
45
46
47
48
49
50
// 六 数学基础 | 2 质数
// #10197. 「一本通 6.2 例 1」Prime Distance
// Prime Distance
#include <bits/stdc++.h>
#define int long long int
using namespace std;
const int SMAX = (1 << 16) + 9;
bitset<(int)1e6+9> mk;

bitset<SMAX> bmk;
vector<int> prime;
void xxs() {
    for(int i = 2; i <= SMAX - 3; i ++) {
        if(!bmk[i]) prime.push_back(i);
        for(int p : prime) {
            if(i * p > SMAX - 3) break;
            bmk[i * p] = 1;
            if(i % p == 0) break;
        }
    }
}

signed main() {
    xxs();
    int l, r;
    while(scanf("%lld%lld", &l, &r) == 2) {
        mk = 0;
        if(l == 1) mk[0] = 1;
        for(int p : prime)
            for(int i = max((l + p - 1) / p, 2ll); i <= r / p; i ++)
                mk[1ll * i * p - l] = 1;
        int beg = -1, now, cj;
        for(int i = 0; i <= r - l; i ++) if(!mk[i]) {beg = i; break; }
        if(beg == -1) {printf("There are no adjacent primes.\n"); continue; }
        int c1, c2, c = INT_MAX;
        int d1, d2, d = INT_MIN;
        for(int i = beg + 1; i <= r - l; i ++) if(!mk[i]) {
            now = i;
            cj = now - beg;
            if(cj < c) {c1 = beg; c2 = now; c = cj; }
            if(cj > d) {d1 = beg; d2 = now; d = cj; }
            beg = now;
        }
        c == INT_MAX ?
        printf("There are no adjacent primes.\n") :
        printf("%lld,%lld are closest, %lld,%lld are most distant.\n",
        c1 + l, c2 + l, d1 + l, d2 + l);
    }
    return 0;
}

练习题

质因数分解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
// 六 数学基础 | 2 质数
// #10198. 「一本通 6.2 练习 1」质因数分解
// P1075 [NOIP2012 普及组] 质因数分解
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 2e9 + 9;

int main() {
    int n, p;
    scanf("%d", &n);
    for(int i = 2; ; i ++)
        if(n % i == 0) {
            p = i;
            break;
        }
    printf("%d", n / p);
    return 0;
}

轻拍牛头

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 六 数学基础 | 2 质数
// #10199. 「一本通 6.2 练习 2」轻拍牛头
// P2926 [USACO08DEC] Patting Heads S
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 1e5 + 9;
const int MAXv = 1e6 + 9;
int d[MAXn], cnt[MAXv], ans[MAXv];

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d", &d[i]),
        cnt[d[i]] ++;
    for(int i = 1; i <= MAXv - 3; i ++) {
        if(!cnt[i]) continue;
        for(int j = 1; j * i <= MAXv - 3; j ++)
            ans[j * i] += cnt[i];
    }
    for(int i = 1; i <= n; i ++)
        printf("%d\n", ans[d[i]] - 1);
    return 0;
}

Goldbach's Conjecture

 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
// 六 数学基础 | 2 质数
// #10200. 「一本通 6.2 练习 3」Goldbach's Conjecture
// Goldbach's Conjecture
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 1e6 + 9;
vector<int> prime;
bitset<MAXn> ved;

void xxs() {
    for(int i = 2; i <= MAXn - 3; i ++) {
        if(!ved[i]) prime.push_back(i);
        for(int p : prime) {
            if(i * p > MAXn - 3) break;
            ved[i * p] = 1;
            if(i % p == 0) break;
        }
    }
    prime.erase(prime.begin());
    ved[0] = ved[1] = ved[2] = 1;
}

int main() {
    xxs();
    int x;
    while(scanf("%d", &x) != EOF && x) {
        for(int p : prime)
            if(!ved[x - p]) {
                printf("%d = %d + %d\n", x, p, x - p);
                break;
            }
    }
    return 0;
}

Sherlock and His Girlfriend

 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
// 六 数学基础 | 2 质数
// #10201. 「一本通 6.2 练习 4」Sherlock and His Girlfriend
// Sherlock and his girlfriend
#include <bits/stdc++.h>
using namespace std;
const int MAXn = 1e5 + 9;

vector<int> prime;
bitset<MAXn> ved;
void xxs(int mx) {
    for(int i = 2; i <= mx + 3; i ++) {
        if(!ved[i]) prime.push_back(i);
        for(int p : prime) {
            if(p * i > mx + 3) break;
            ved[p * i] = 1;
            if(i % p == 0) break;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    n <= 2 ? printf("1\n") : printf("2\n");
    xxs(n + 3);
    for(int i = 1; i <= n; i ++)
        ved[i + 1] ? printf("2 ") : printf("1 ");
    return 0;
}

樱花

 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
40
41
42
43
// 六 数学基础 | 2 质数
// #10202. 「一本通 6.2 练习 5」樱花
// P1445 [Violet] 樱花
#include <bits/stdc++.h>
#define lli long long int
using namespace std;
const lli mod = 1e9 + 7;
const int MAXn = 1e6 + 9;
vector<int> prime;
int zys[MAXn];
int tms[MAXn];

bitset<MAXn> bs;
void xxs(int mx) {
    for(int i = 1; i <= mx + 3; i ++) zys[i] = i;
    for(int i = 2; i <= mx + 3; i ++) {
        if(!bs[i]) prime.push_back(i);
        for(int p : prime) {
            if(p * i > mx + 3) break;
            bs[p * i] = 1;
            zys[p * i] = p;
            if(i % p == 0) break;
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    xxs(n);
    lli ans = 1;
    for(int i = 2; i <= n; i ++) {
        int now = i;
        while(now != 1) {
            tms[zys[now]] ++;
            now /= zys[now];
        }
    }
    for(int i = 1; i <= n; i ++)
        (ans *= (tms[i] % mod * 2 % mod + 1) % mod) %= mod;
    printf("%lld", ans);
    return 0;
}