[POJ 3048] Max Factor【欧拉筛】
Problem:
Time Limit: 1000MS | Memory Limit: 65536K |
Description
(Recall that a prime number is just a number that has no divisors except for 1 and itself. The number 7 is prime while the number 6, being divisible by 2 and 3, is not).
Given a set of N (1 <= N <= 5,000) serial numbers in the range 1..20,000, determine the one that has the largest prime factor.
Input
* Lines 2..N+1: The serial numbers to be tested, one per line
Output
Sample Input
4 36 38 40 42
Sample Output
38
Hint
19 is a prime factor of 38. No other input number has a larger prime factor.
Source
Solution:
先用欧拉筛筛出 [2, 20000] 上的素数,对每个编号分解质因数,求出其最大质因数。
注意有多组数据,以及题目要求的是“有最大质因数”,而不是“有最多质因数”。
Code: O(TNP), P为素数个数 [200K, 47MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; const int UPRANGE = 20000; int prm[UPRANGE >> 1], prmSize; bool isprm[UPRANGE + 2]; inline void initPrime(){ memset(isprm, 1, sizeof(isprm)); isprm[0] = isprm[1] = 0, prmSize = 0; for(register int i = 2; i <= UPRANGE; i++){ if(isprm[i]) prm[++prmSize] = i; for(register int j = 1; j <= prmSize && i * prm[j] <= UPRANGE; j++){ isprm[i * prm[j]] = 0; if(i % prm[j] == 0) break; } } } int N, curid; int ans, mxfac; int main(){ initPrime(); while(scanf("%d", &N) != EOF){ // Notice that input contains several test cases mxfac = 0; while(N--){ scanf("%d", &curid); int tmp = curid, curfac; for(register int i = 1; i <= prmSize && prm[i] <= tmp; i++) while(tmp % prm[i] == 0) tmp /= prm[i], curfac = prm[i]; if(curfac > mxfac) mxfac = curfac, ans = curid; } printf("%d\n", ans); } return 0; }
发表评论