[数据结构与算法]数学 - 质数、约数

1620：质因数分解

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n;
	cin >> n;
	
	for (int i = 2; i <= n / i; i ++) {
		if (n % i == 0) {
			cout << n / i;
			break;
		}
	}

	return 0;
}

1621：轻拍牛头

• O(n * sqrt(a[i]))

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;
int n, a[N], cnt[M];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) {
		scanf("%d", &a[i]);
		cnt[a[i]] ++;
	}
	
	for (int i = 1; i <= n; i ++) {
		int t = sqrt(a[i]), ans = 0;		
		for (int j = 1; j <= t; j ++) {
			if (a[i] % j == 0) {
				ans += cnt[j] + cnt[a[i] / j];
			}
		}
		if (a[i] == t * t) ans -= cnt[t];
		printf("%d\n", ans - 1);
	}

	return 0;
}

• O（M * lnM）

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;
int n, a[N], b[M], cnt[M];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) {
		scanf("%d", &a[i]);
		cnt[a[i]] ++;
	}
	
	for (int i = 1; i <= 1e6; i ++) {
		if (!cnt[i]) continue;
		
		for (int j = i; j <= 1e6; j += i) {
			b[j] += cnt[i];
		}
	}

	for (int i = 1; i <= n; i ++) {
		printf("%d\n", b[a[i]] - 1);
	}

	return 0;
}

1622：Goldbach’s Conjecture

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
int n, a[N + 10];
int m, p[N + 10];	//m个质数

int main() {
	for (int i = 2; i <= N; i ++) {
		if (!a[i]) {
			p[++ m] = i;
			for (int j = 2; i * j <= N; j ++) {
				a[i * j] = 1;
			}
		}
	}
	
	while (scanf("%d", &n)) {
		if (n == 0) break;
		
		//小于1百万的偶数都满足猜想 
		for (int i = 1; i <= m; i ++) {
			if (!a[n - p[i]]) {
				printf("%d = %d + %d\n", n, p[i], n - p[i]);
				break;
			}
		}
	}

	return 0;
}

1623：Sherlock and His Girlfriend

#include <bits/stdc++.h>
using namespace std;

int n;
bool a[100009];

int main() {
	cin >> n;
	
	if (n <= 2) {
		printf("1\n");
	}
	else {
		printf("2\n");
	}
		
	for (int i = 2; i <= n + 1; i ++) {
		if (!a[i]) {
			for (int j = 2 * i; j <= n + 1; j += i) {
				a[j] = true;
			}
		}
	}
	
	for (int i = 2; i <= n + 1; i ++) {
		if (!a[i]) printf("1 ");
		else printf("2 ");
	}		
	
	return 0;
}

1624：樱花

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
int n, a[1000009];

void f(int x) {
	for (int i = 2; i * i <= x; i ++) {
		while (x % i == 0) {
			a[i] ++;
			x /= i;
		}
	}
	if (x > 1) a[x] ++;
}

int main() {
	cin >> n;
	for (int i = 2; i <= n; i ++) {
		f(i);
	}
	
	long long res = 1;
	for (int i = 2; i <= n; i ++) {
		if (a[i]) {
			res = res * (2 * a[i] + 1) % MOD;
		}
	}
	cout << res;

	return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 9, MOD = 1e9 + 7;
int n, a[N];
int m, p[N];	//m个质数 

int main() {
	cin >> n;	
	for (int i = 2; i <= n; i ++) {
		if (!a[i]) {
			p[++ m] = i;
			
			for (int j = i; j <= n / i; j ++) {
				a[i * j] = 1;
			}
		}
	}

	long long res = 1;
	for (int i = 1; i <= m; i ++) {
		long long t = p[i];
		int cnt = 0;
		while (t <= n) {
			cnt += n / t;
			t *= p[i];
		}
		 
		res = res * (2 * cnt + 1) % MOD;
	}
	cout << res;

	return 0;
}

1619：Prime Distance

#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1e6 + 10;
int a[N], p[N], n;

int main() {
	for (int i = 2; i < 50000; i ++) {
		if (!a[i]) p[++ n] = i;
		
		for (int j = 1; p[j] * i < 50000; j ++)	{
			a[p[j] * i] = 1;	//合数 
			if (i % p[j] == 0)  break;
		}			
	}	
	 
	LL l, r;
	while (cin >> l >> r) {
		memset(a, 0, sizeof(a));
		if (l == 1) a[1 - l] = 1;					//1不是质数
		
		for (int i = 1; i <= n; i ++) {
			LL x = (l + p[i] - 1) / p[i] * p[i];	//上取整 
			if (x == p[i]) x += p[i];
	
			for (LL j = x; j <= r; j += p[i]) {
				a[j - l] = 1;						//j是合数 
			}
		}
			
		LL prime, cnt = 0, x, y, maxx = 0, minn = 1e6;
		bool flag = true;
		for (LL j = l; j <= r; j ++) {
			if (!cnt && !a[j - l] ) {
				prime = j;
				cnt ++;
			}
			else if (cnt && !a[j - l]) {
				if (j - prime > maxx) {
					maxx = j - prime;
					x = j;
				}
				if (j - prime < minn) {
					minn = j - prime;
					y = j; 
				} 
				prime = j;
				cnt ++;
			}
		}
		
		if (cnt < 2) {
			puts("There are no adjacent primes.");
		}
		else {
			printf("%d,%d are closest, %d,%d are most distant.\n", y - minn, y, x - maxx, x);
		}	
	}

    return 0;
}

阅读世界，共赴山海

423全民读书节，邀你共读