首页 > 代码库 > 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 (数论)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。