結果
問題 | No.371 ぼく悪いプライムじゃないよ |
ユーザー |
![]() |
提出日時 | 2016-07-05 04:58:14 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 42 ms / 1,000 ms |
コード長 | 2,799 bytes |
コンパイル時間 | 1,460 ms |
コンパイル使用メモリ | 100,112 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-30 18:24:03 |
合計ジャッジ時間 | 3,754 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 42 |
ソースコード
#include <algorithm>#include <cassert>#include <climits>#include <cmath>#include <cstdio>#include <cstdlib>#include <deque>#include <iomanip>#include <iostream>#include <limits>#include <map>#include <queue>#include <set>#include <sstream>#include <stack>#include <string>#include <vector>#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))#define rep(i,n) FOR(i,0,n)#define pb push_back#define eb emplace_back#define all(v) begin(v), end(v)#define debug(x) cerr<< #x <<": "<<x<<endl#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endlusing namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<int, int> i_i;typedef pair<i_i, int> p_i;typedef vector<int> vi;typedef vector<vector<int> > vvi;typedef vector<ll> vll;typedef vector<vector<ll> > vvll;typedef vector<char> vc;typedef vector<vector<char> > vvc;typedef vector<double> vd;typedef vector<vector<double> > vvd;template<class T> using vv=vector<vector< T > >;typedef deque<int> di;typedef deque<deque<int> > ddi;// cout vectortemplate<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {int len = v.size();for (int i = 0; i < len; ++i) {s << v[i]; if (i < len - 1) s << "\t";}return s;}// cout 2-dimentional vectortemplate<typename T> ostream& operator<<(ostream& s, const vector< vector<T> >& vv) {int len = vv.size();for (int i = 0; i < len; ++i) {s << vv[i] << endl;}return s;}int MAX_PRIME; // in this problem up to 10^6deque<bool> isprime;vector<int> primes;void init_prime(int mp) {MAX_PRIME = mp;isprime.resize(MAX_PRIME+1, true);isprime[0] = isprime[1] = false;primes.clear();for(int i = 2; i <= MAX_PRIME; i++) {if (isprime[i]) {primes.push_back(i);for(int j = i*2; j <= MAX_PRIME; j += i) {isprime[j] = false;}}}}ll min_factor(ll n) {rep (i, upper_bound(all(primes), (int)sqrt(n)) - begin(primes)) {if ( n % primes[i] == 0 ) {return primes[i];}}return (ll)INT_MAX;}int main() {ll l, h;cin >> l >> h;init_prime(1000000);int maxminfact = 2;ll maxminproduct = h - (h % 2 == 1 ? 1 : 0);for (int i = upper_bound(all(primes), (int)sqrt(h)) - begin(primes) - 1; i >= 0; --i) {if ( primes[i] < maxminfact ) {break;}for (ll j = h / primes[i]; j * primes[i] >= l; --j) {int tmp_fact = min(primes[i], (int)min_factor(j));if ( tmp_fact > maxminfact ) {maxminfact = tmp_fact;maxminproduct = j * primes[i];}}}printf("%lld\n", maxminproduct);return 0;}