題目:給你一個整數 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;
- }
来源: http://www.bubuko.com/infodetail-2109426.html