UVa 11466 - Largest Prime Divisor

时间:2022-12-10 19:39:47

題目:給你一個整數n(不超過14位)。求出他的最大的素數因子。假设仅仅有一個素數因子輸出-1。

分析:數論。

直接打表計算10^7內的全部素數因子,然後用短除法除n。記錄最大的因子就可以。

假设最後下的數字不是1,則它就是最大的素數因子。

說明:注意n可能為負數。

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath> using namespace std; int visit[10000001];
int prime[10000001]; int main()
{
memset(visit, 0, sizeof(visit));
int count = 0;
for (int i = 2; i < 10000001; ++ i) {
if (!visit[i]) prime[count ++] = i;
for (int j = 0; j < count && i*prime[j] < 10000001; ++ j)
visit[i*prime[j]] = 1;
} long long n,m;
while (cin >> n && n) {
if (n < 0) n = -n;
int size = 0;
for (int i = 0; i < count; ++ i) {
if (n < prime[i]) break;
if (n%prime[i] == 0) {
m = prime[i];
++ size;
while (n%m == 0) n /= m;
}
}
if (n != 1) {
m = n;
++ size;
} if (size > 1)
cout << m << endl;
else cout << "-1" << endl;
}
return 0;
}