#62393 (C#(csc)) No.308 素数は通れません

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	kuuso1
提出日時	2015-12-04 01:26:00
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	41 ms / 1,000 ms
コード長	2,928 bytes
コンパイル時間	1,413 ms
コンパイル使用メモリ	113,896 KB
実行使用メモリ	24,500 KB
最終ジャッジ日時	2024-11-27 18:38:32
合計ジャッジ時間	7,868 ms
ジャッジサーバーID （参考情報）	judge1 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	30 ms 24,424 KB
testcase_01	AC	30 ms 24,424 KB
testcase_02	AC	30 ms 24,300 KB
testcase_03	AC	30 ms 24,112 KB
testcase_04	AC	30 ms 22,196 KB
testcase_05	AC	30 ms 24,364 KB
testcase_06	AC	30 ms 24,292 KB
testcase_07	AC	30 ms 24,236 KB
testcase_08	AC	30 ms 24,292 KB
testcase_09	AC	30 ms 24,296 KB
testcase_10	AC	29 ms 22,196 KB
testcase_11	AC	29 ms 24,420 KB
testcase_12	AC	30 ms 24,364 KB
testcase_13	AC	30 ms 24,360 KB
testcase_14	AC	30 ms 24,496 KB
testcase_15	AC	30 ms 24,300 KB
testcase_16	AC	31 ms 24,244 KB
testcase_17	AC	30 ms 24,300 KB
testcase_18	AC	30 ms 24,300 KB
testcase_19	AC	30 ms 24,172 KB
testcase_20	AC	30 ms 24,368 KB
testcase_21	AC	30 ms 24,172 KB
testcase_22	AC	31 ms 22,456 KB
testcase_23	AC	30 ms 24,364 KB
testcase_24	AC	30 ms 24,300 KB
testcase_25	AC	29 ms 24,296 KB
testcase_26	AC	29 ms 22,192 KB
testcase_27	AC	30 ms 24,296 KB
testcase_28	AC	30 ms 24,244 KB
testcase_29	AC	31 ms 24,368 KB
testcase_30	AC	30 ms 24,296 KB
testcase_31	AC	30 ms 24,240 KB
testcase_32	AC	30 ms 24,168 KB
testcase_33	AC	31 ms 24,300 KB
testcase_34	AC	30 ms 22,196 KB
testcase_35	AC	31 ms 24,296 KB
testcase_36	AC	30 ms 22,200 KB
testcase_37	AC	30 ms 24,364 KB
testcase_38	AC	30 ms 22,196 KB
testcase_39	AC	31 ms 24,500 KB
testcase_40	AC	30 ms 24,300 KB
testcase_41	AC	30 ms 24,368 KB
testcase_42	AC	31 ms 24,296 KB
testcase_43	AC	31 ms 24,420 KB
testcase_44	AC	31 ms 24,300 KB
testcase_45	AC	31 ms 24,172 KB
testcase_46	AC	30 ms 24,424 KB
testcase_47	AC	31 ms 24,296 KB
testcase_48	AC	30 ms 24,176 KB
testcase_49	AC	31 ms 24,424 KB
testcase_50	AC	31 ms 24,492 KB
testcase_51	AC	30 ms 24,292 KB
testcase_52	AC	30 ms 24,300 KB
testcase_53	AC	30 ms 24,292 KB
testcase_54	AC	30 ms 24,044 KB
testcase_55	AC	31 ms 24,304 KB
testcase_56	AC	32 ms 22,068 KB
testcase_57	AC	31 ms 24,432 KB
testcase_58	AC	31 ms 24,300 KB
testcase_59	AC	30 ms 24,172 KB
testcase_60	AC	31 ms 24,308 KB
testcase_61	AC	31 ms 24,112 KB
testcase_62	AC	31 ms 24,236 KB
testcase_63	AC	37 ms 24,044 KB
testcase_64	AC	30 ms 24,164 KB
testcase_65	AC	31 ms 24,368 KB
testcase_66	AC	31 ms 24,304 KB
testcase_67	AC	30 ms 24,116 KB
testcase_68	AC	30 ms 24,304 KB
testcase_69	AC	32 ms 24,368 KB
testcase_70	AC	31 ms 24,496 KB
testcase_71	AC	30 ms 24,304 KB
testcase_72	AC	31 ms 24,496 KB
testcase_73	AC	30 ms 24,428 KB
testcase_74	AC	31 ms 24,300 KB
testcase_75	AC	30 ms 24,372 KB
testcase_76	AC	33 ms 24,372 KB
testcase_77	AC	30 ms 24,368 KB
testcase_78	AC	30 ms 24,364 KB
testcase_79	AC	30 ms 22,196 KB
testcase_80	AC	33 ms 24,176 KB
testcase_81	AC	41 ms 24,296 KB
testcase_82	AC	30 ms 22,068 KB
testcase_83	AC	31 ms 24,496 KB
testcase_84	AC	38 ms 22,576 KB
testcase_85	AC	30 ms 24,172 KB
testcase_86	AC	38 ms 24,240 KB
testcase_87	AC	38 ms 24,428 KB
testcase_88	AC	31 ms 24,368 KB
testcase_89	AC	31 ms 24,296 KB
testcase_90	AC	39 ms 24,496 KB
testcase_91	AC	32 ms 24,364 KB
testcase_92	AC	30 ms 24,364 KB
testcase_93	AC	31 ms 24,164 KB
testcase_94	AC	31 ms 24,372 KB
testcase_95	AC	31 ms 22,580 KB
testcase_96	AC	37 ms 24,364 KB
testcase_97	AC	30 ms 24,300 KB
testcase_98	AC	30 ms 24,372 KB
testcase_99	AC	39 ms 24,172 KB
testcase_100	AC	38 ms 24,364 KB
testcase_101	AC	39 ms 22,324 KB
testcase_102	AC	31 ms 24,368 KB
testcase_103	AC	31 ms 24,300 KB
testcase_104	AC	32 ms 22,584 KB
testcase_105	AC	31 ms 22,196 KB
testcase_106	AC	38 ms 24,428 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

raw source code

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using BI=System.Numerics.BigInteger;

class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}

class Sol{
	public void Solve(){
		
		
		int ans=0;
		int N2=0;
		if(N<100){
			N2=(int)N;
			switch(N2){
				case 4:	ans=3;break;
				case 6:	ans=5;break;
				case 8:	ans=7;break;
				case 9:	ans=7;break;
				case 10:	ans=7;break;
				case 15:	ans=7;break;
				case 16:	ans=7;break;
				case 22:	ans=7;break;
				case 33:	ans=8;break;
				case 57:	ans=8;break;
				case 65:	ans=8;break;
				case 12:	ans=11;break;
				case 14:	ans=13;break;
				case 20:	ans=19;break;
				case 21:	ans=19;break;
				case 24:	ans=23;break;
				case 25:	ans=23;break;
				default:
					if(N%8==1){
						ans=14;
					}else{
						ans=8;
					}break;
			}
			Console.WriteLine(ans);
			return;
		}
		
		Console.WriteLine((N%8==1 && IsPrime(N-8))?14:8);
		
	}
	String S;
	BI N;
	public Sol(){
		S=rs();
		N=BI.Parse(S);
	}

	static bool IsPrime(BI x){
		if(x==2)return true;
		if((x==1) || (x&1)==0)return false;
		if(x<(BI)1e12){
			for(BI t=2;t*t<=x;t++){
				if(x%t==0)return false;
			}
			return true;
		}
		return MillerRabinTest(x);
	}
	
	static bool MillerRabinTest(BI n){
		int rep=20;
		BI d=n-1;
		// (n-1)=2^s*d
		while((d&1)==0)d>>=1;
		
		var rnd=new Xor128();
		BI a=1+((BI)rnd.Next())%(n-2);
		
		while(rep>0){
			rep--;
			a=1+((BI)rnd.Next()*a)%(n-2);
			BI t=d;
			BI y=ModPowBI(a,t,n);
			while(t!=(n-1) && y!=1 && y!=n-1){
				y=y*y%n;
				t<<=1;
			}
			if(y!=(n-1) && (t&1)==0)return false;
		}
		return true;
	}
	
	static BI ModPowBI(BI a,BI t,BI mod){
		BI ret=1;
		while(t>0){
			if((t&1)==1){ret*=a;ret%=mod;};
			a=a*a;a%=mod;
			t>>=1;
		}
		return ret;
	}
	


	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(){return Console.ReadLine().Split(' ');}
	static int[] ria(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>int.Parse(e));}
	static long[] rla(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>long.Parse(e));}
	static double[] rda(){return Array.ConvertAll(Console.ReadLine().Split(' '),e=>double.Parse(e));}
}


class Xor128{
	static uint x = 123456789;
	static uint y = 362436069;
	static uint z = 521288629;
	static uint w = 88675123; 
	uint t;
	
	public Xor128(){
	}
	
	public Xor128(uint seed){
		z ^= seed;
		z ^= z >> 21; z ^= z << 35; z ^= z >> 4;
	}
	
	
	public uint Next(){
		t = x ^ (x << 11);
		x = y; y = z; z = w;
		return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
	}
	public int Next(int ul){
		return NextI(0,ul-1);
	}
	public int NextI(int from,int to){
		int mod=to-from+1;
		int ret=(int)(Next()%mod);
		return ret+from;
	}
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード