素数

Prime Distance

题面翻译

  • 给定两个正整数 \(l,r\)，求 \([l,r]\) 间 相邻 的两个差最大的质数和 相邻 的两个差最小的质数。如果区间内质数个数 \(\le 1\)，输出 There are no adjacent primes.。
  • \(1\le l<r\le 2^{31}-1\)，\(r-l\le 10^6\)。

样例输入 #1

1
2
2 17
14 17

样例输出 #1

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

对于一个合数n，一定有一个不超过根号n的质因数

由于数据范围不大

我们可以直接预处理出素数

然后对所有素数标记在L,R查的倍数，然后扫一遍就可以知道没有被标记的一定是素数，这样直接判断即可。

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
#include<bits/stdc++.h>
using namespace std;
#define N 2000100
#define ll long long 
#define inf 2147483647
int l, r, p[N], m, f[N];
bool vis[N];

int main() {
    int cnt = 0;
    for(int i = 2; i < 50000; ++i) {
        if(!vis[i]) p[++cnt] = i;
        for(int j = 1; j <= cnt && p[j] * i < 50000; ++j) {
            vis[i * p[j]] = 1;
            if(i % p[j] == 0) break;
        }
    }
    while(cin>>l>>r)
    {
        memset(vis, 0, sizeof(vis));
        if(l == 1) vis[0] = 1;
        for(int i = 1; i <= cnt; ++i) {
            for(int j = l / p[i]; j <= r / p[i]; ++j) {
                if(j > 1) vis[p[i] * j - l] = 1;
            }
        }
        //对质数的倍数进行筛选
        m = 0;
        for(int i = l; i <= r; ++i) {
            if(!vis[i - l]) f[++m] = i;
            if(i == r) break;
        }
        //对质数进行存储
        int mx = 0, mn = inf, x_1 = 0, x_2 = 0, y_1 = 0, y_2 = 0;
        for(int i = 2; i <= m; ++i) 
        {
            if(f[i] - f[i - 1] > mx) {
                mx = f[i] - f[i - 1];
                x_1 = f[i - 1], y_1 = f[i]; 
            }
            if(f[i] - f[i - 1] < mn) {
                mn = f[i] - f[i - 1];
                x_2 = f[i - 1], y_2 = f[i];
            }
        }
        if(!mx) puts("There are no adjacent primes.");
        else cout << x_2 << ',' << y_2 << " are closest, " << x_1 << ',' << y_1 << " are most distant.\n";
    }
    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
44
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=1e6+7;
int is_pri[N],pri[N],ans[N],cnt=0;
void init()
//欧拉筛分解
{
	for(int i=2;i<N;i++){
		if(!is_pri[i]) pri[++cnt]=i;
		for(int j=1;j<=cnt&&pri[j]*i<N;j++){
			is_pri[i*pri[j]]=1;
			if(i%pri[j]==0) break;
		}
	}
}
signed main(){
	int n,res,tmp;
	init();
	cin>>n;
	res=1;
	for(int i=1;i<=n;i++){
		res*=i;
		tmp=sqrt(res);
        //进行质因数分解。
		for(int j=1;j<=cnt&&pri[j]<tmp;j++){
			while(res%pri[j]==0){
				res/=pri[j];
				ans[pri[j]]++;
			}
		}
        //如果还有剩下，并且不能分解了
        //判断是否是素数，然后存储即可
		if(res<N&&!is_pri[res]){
			ans[res]++;
			res=1;
		}
	}
	for(int i=2;i<N;i++){
		if(ans[i]) cout<<i<<" "<<ans[i]<<"\n";
	}
	return 0;
}
收藏[1285]PID[89486925]_标题[无题]画师[Mobu]UID[19025318]