結果

問題 No.12 限定された素数
ユーザー diginatudiginatu
提出日時 2014-11-24 01:34:12
言語 D
(dmd 2.106.1)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,322 bytes
コンパイル時間 382 ms
コンパイル使用メモリ 6,784 KB
最終ジャッジ日時 2024-04-27 02:05:49
合計ジャッジ時間 1,028 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
このコードへのチャレンジ
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
Main.d(14): Error: instead of C-style syntax, use D-style `bool[5000001] is_prime`

ソースコード

diff #

import std.stdio, std.string, std.conv
	,std.array,std.algorithm, std.range
	,std.math;


void main(){
	readln();
	auto Ao = readln().strip().split().map!(to!int)();
	int A;
	foreach(int t; Ao) {
		A += 1<<t;
	}

	bool is_prime[5000001];

	void Eratosthenes(int lim){
		is_prime[] = true;
		is_prime[0] = false;
		is_prime[1] = false;
		for(int p=2; p*p<=lim; p++) {
			if(is_prime[p]){
				for(int k=p*p; k<=lim; k+=p) is_prime[k] = false;
			}
		}
	}

	Eratosthenes(5000000);

	int st = 1;
	int maxr = 0;
	bool ing = true;
	int At = A;
	foreach(int i; 1 .. 5000001) {
		if(is_prime[i]) {
			bool inc = true;
			char[] tpr = i.to!(char[]);
			auto a = tpr.map!(a => a-'0')().array;
			a.sort().uniq();

			int tt = 0;
			foreach(int t; a) {
				tt |= 1<<t;
			}

			foreach(int t; a) {
				if(A&1<<t) {
				} else {
					inc = false;
					break;
				}
			}

			if(ing) {
				if(inc) {
					At &= ~tt;
				} else {
					if(!At) {
						maxr = max(maxr, i - 1 - st);
					}
					ing = false;
				}
			} else {
				if(inc) {
					At = A;
					At &= ~tt;
					ing = true;
					st = i;
				}
			}
		} else if(!ing) {
			At = A;
			ing = true;
			st = i;
		}
	}

	if(ing && !At)
		maxr = max(maxr, 5000000 - st);
	
	writeln( maxr==0?-1:maxr );
}
0