质数

3 区间筛法

196. 质数距离https://www.acwing.com/problem/content/198/

给定两个整数L和U，你需要在闭区间[L,U]内找到距离最接近的两个相邻质数C1和C2（即C2-C1是最小的），如果存在相同距离的其他相邻质数对，则输出第一对。

同时，你还需要找到距离最远的两个相邻质数D1和D2（即D1-D2是最大的），如果存在相同距离的其他相邻质数对，则输出第一对。

输入格式

每行输入两个整数L和U，其中L和U的差值不会超过1000000。

输出格式

对于每个L和U ，输出一个结果，结果占一行。

结果包括距离最近的相邻质数对和距离最远的相邻质数对。（具体格式参照样例）

如果L和U之间不存在质数对，则输出“There are no adjacent primes.”。

数据范围

输入样例：

2 17
14 17

输出样例：

2,3 are closest, 7,11 are most distant.
There are no adjacent primes.

判断质数之间距离的大小说明我们先要求出属于这个区间的质数，数据范围太大了，d|n 的话，只需要判断出sqre(n)的即可，然后扩大，把区间内的倍数标记筛出，注意L = 1,着一种情况
具体的看代码吧

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int m;
int v[maxn],prime[maxn];
int s[maxn],res[maxn];
int l,r;
void primes(int n){
    for(int i = 2; i <= n; i++){
        if(!v[i]) prime[++m] = i;
        for(int j = 1;j <= m && i * prime[j] <= n; j++){
            v[i * prime[j]] = 1;
            if(i % prime[j] == 0) break;
        }
    }
}
int main(){
    primes(50000);//sqrt(2的31次方）因为d|n的话,d <= sqrt(n);
    while(scanf("%d%d",&l,&r)!=EOF){
        memset(s,0,sizeof(s));
        if(l == 1) s[0] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = ceil(l / prime[i]); j <= floor(r / prime[i]); j++)
                if(j != 1)
                    s[j * prime[i] - l] = 1;//数组平移
        }


        //标记质数
        int num = 0;
        for(int i = 0; i <= r - l; i++){
            if(!s[i])
                res[++num] = i + l;
        }

        int maxx = 0,minn = 0x3f3f3f3f;
        int l1,r1,l2,r2;
        //一个个相邻的质数去比较，找最值
        for(int i = 1; i < num; i++){
            if(maxx < res[i + 1] - res[i]){
                maxx = res[i + 1] - res[i];
                l1 = res[i];
                r1 = res[i + 1];
            }
            if(minn > res[i + 1] - res[i]){
                minn = res[i + 1] - res[i];
                l2 = res[i];
                r2 = res[i + 1];
            }
        }

        if(maxx == 0 || minn == 0x3f3f3f3f)
            puts("There are no adjacent primes.");
        else printf("%d,%d are closest, %d,%d are most distant.
",l2,r2,l1,r1);
    }
    return 0;
}

View Code

197. 阶乘分解 https://www.acwing.com/problem/content/199/

给定整数 N ，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的

输入格式

一个整数N。

输出格式

N! 分解质因数后的结果，共若干行，每行一对

数据范围

输入样例：

输出样例：

2 3
3 1
5 1

样例解释

思路一：先求出n的质因子，然后分别判断1 - n中的每一个数，时间复杂度O(n *n½) 会超时

思路二:在思路一的基础上，不妨把判断的方法改一下，用倍数法，对于每个质因子p,求n内有几个p,p²,p³,....时间复杂度为O(nlogn)求和是logn，一共是n个数

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1e6 + 10;
 4 int n,m;
 5 bool vis[maxn];
 6 int p[maxn];
 7 void get(){
 8     for(int i = 2; i <= n; i++){
 9         if(!vis[i]){
10             vis[i] = 1;p[++m] = i;
11         }
12         for(int j = 1; j <= m && i * p[j] <= n; j++){
13             vis[i * p[j]] = 1;
14             if(i % p[j] == 0) break;
15         }
16     }
17 }
18 int main(){
19     ios::sync_with_stdio(0);
20     cin >> n;
21     get();
22     for(int i = 1; i <= m; i++){
23         int t = n,c = 0;
24         while(t){
25             c += t / p[i];
26             t /= p[i];
27         }
28         cout << p[i] << " " << c << endl;
29     }
30     return 0;
31 }

View Code