UVA 294 294 - Divisors (数论)

本文主要是介绍UVA 294 294 - Divisors (数论)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA 294 - Divisors

题目链接

题意：求一个区间内，因子最多的数字。
思路：由于区间保证最多1W个数字，因子可以遍历区间，然后利用事先筛出的素数求出质因子，之后因子个数为所有(质因子的个数+1)的积

代码：

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;const int N = 35005;
int prime[N], pn = 0, vis[N];
int t, a, b;int cal(int num) {int ans = 1;for (int i = 0; i < pn && prime[i] <= num; i++) {if (num % prime[i]) continue;int count = 1;while (num % prime[i] == 0) {count++;num /= prime[i];}ans *= count;}return ans;
}void solve() {int ans, Max = 0;for (int i = a; i <= b; i++) {if (Max < cal(i)) {ans = i;Max = cal(i);}}printf("Between %d and %d, %d has a maximum of %d divisors.\n", a, b, ans, Max);
}int main() {for (int i = 2; i < N; i++) {if (vis[i]) continue;prime[pn++] = i;for (int j = i; j < N; j += i)vis[j] = 1;}scanf("%d", &t);while (t--) {scanf("%d%d", &a, &b);solve();}return 0;
}

这篇关于UVA 294 294 - Divisors (数论)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---