結果
問題 |
No.12 限定された素数
|
ユーザー |
![]() |
提出日時 | 2017-04-30 22:48:20 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 961 ms / 5,000 ms |
コード長 | 1,597 bytes |
コンパイル時間 | 375 ms |
コンパイル使用メモリ | 42,368 KB |
実行使用メモリ | 19,076 KB |
最終ジャッジ日時 | 2024-11-24 09:37:43 |
合計ジャッジ時間 | 26,272 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 26 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:83:30: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 83 | scanf("%d", &a[i]); | ~~~~~^~~~~~~~~~~~~
ソースコード
#include<cstdio> #include<vector> using namespace std; #define L_MAX 5000000 class prime_t { public: int x; int c[10]; prime_t(int x) { int i; for(i=0;i<10;i++) c[i]=0; this->x=x; for(;x;x/=10) { c[x%10]=1; } } }; vector<prime_t> prime; void init(void) { int i, j; prime.clear(); prime.reserve(L_MAX/4); prime.push_back(prime_t(0)); prime.push_back(prime_t(2)); for(i=3;i<=L_MAX;i+=2) { for(j=3;j*j<=i;j+=2) { if(i%j==0) break; } if(j*j>i) { prime.push_back(prime_t(i)); } } prime.push_back(prime_t(L_MAX+1)); } int max_u(int& m, int v) { if(m<v) { m=v; return 1; } return 0; } int main(void) { int n, i; vector<int> a, b, c, f; int ps, pe, max, d, k, l, ok, ng; init(); while(scanf("%d", &n)==1) { a.resize(n); f.clear(); f.resize(10); c.clear(); c.resize(10); for(i=0;i<n;i++) { scanf("%d", &a[i]); f[a[i]]=1; } ok=ng=0; max=-1; ps=1; for(pe=1;pe+1<prime.size();pe++) { for(i=0;i<10;i++) { d=prime[pe].c[i]; if(d==0) continue; if(c[i]==0) { if(f[i]) ok++; else ng++; } c[i]++; } if(ok==n) { for(;ps<=pe;ps++) { if(ng==0) break; for(i=0;i<10;i++) { d=prime[ps].c[i]; if(d==0) continue; c[i]--; if(c[i]==0) { if(f[i]) ok--; else ng--; } } } } if(ok==n && ng==0) { k=prime[ps-1].x+1; l=prime[pe+1].x-1; if(max_u(max, l-k)) { // printf("l=%d k=%d max=%d\n", l, k, max); } } } printf("%d\n", max); } return 0; }