Algoogle

Algorithm for Programming Contest

PKU 3048 Max Factor

Category: PKU Tag: math

Max Factor

問題概要


解法


素数列作っておいて割って試すだけ.

コード


(3048.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <vector>

using namespace std;

vector<int> primes;
bool np[20010];

void gen(){
    np[0] = np[1] = 1;
    for(int i = 2; i < 20010; i++)
        if(!np[i]){
            primes.push_back(i);
            for(int j = i * i; j < 20010; j += i)
                np[j] = 1;
        }
}

int N, M, ans, pos;

int main(){
    gen();
    scanf("%d", &N);
    ans = 1;
    while(N --> 0){
        int num; scanf("%d", &num);
        for(int i = pos; primes[i] <= num; i++)
            if(num % primes[i] == 0 && primes[i] > M){
                ans = num;
                pos = i;
                M = primes[i];
            }
    }
    printf("%d\n", ans);
    return 0;
}

Comments