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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <list>
#include <cmath>

typedef std::list<long long> list;

int main(int argc, char** argv) {
	long long k;
	long long N;
	long long max_primes = 10000000;
	long long max_N;
	long long value;
	list p;
	list primes;

	std::cin >> k;
	std::cin >> N;

	primes.push_back(2);

	for (long long i = 3; i < sqrt(N) + 1 && i < max_primes; i += 2) {
		int is_prime = 1;
		list::iterator it = primes.begin();
		while (*it < sqrt(i) + 1) {
			if (! (i % *it)) {
				is_prime = 0;
				break;
			}
			it++;
		}
		if (is_prime) {
			primes.push_back(i);
		}
	}

	for (long long i = 0; i < k; i++) {
		std::cin >> value;
		if (value < N) {
		    p.push_back(value);
		    list::iterator it = primes.begin();
		    while (*it != value && it != primes.end()) it++;
		    if (it != primes.end()) {
		    	primes.erase(it);
		    }
		} else if (value == N) {
			std::cout << N << std::endl;
			return 0;
		}
	}

	if (p.begin() != p.end()) {
		p.sort();

		max_N = N;
		while (max_N > 1) {
			N = max_N;
			//std::cout << max_N << std::endl;
			list::iterator it = primes.begin();
			while (it != primes.end() && (max_N % *it)) {
				it++;
			}
			if (it == primes.end()) {
				//std::cout << max_N << std::endl;
				list::iterator it2 = p.begin();
				while (N > 1 && it2 != p.end()) {
					while (!(N % *it2)) {
						N /= *it2;
					}
					it2++;
				}
				if (N == 1) {
					std::cout << max_N << std::endl;
					return 0;
				}
			}
			max_N--;
		}
	}
	std::cout << max_N << std::endl;

    return 0;
}