UVa 11466 - Largest Prime Divisor

題目：給你一個整數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; }

总结

以上是生活随笔为你收集整理的UVa 11466 - Largest Prime Divisor的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。