#61738 (Java21) No.308 素数は通れません

提出ソース

結果

問題	No.308 素数は通れません
ユーザー	ぴろず
提出日時	2015-12-01 10:45:47
言語	Java21 (openjdk 21)
結果	WA
実行時間	-
コード長	1,601 bytes
コンパイル時間	6,193 ms
コンパイル使用メモリ	76,024 KB
実行使用メモリ	57,816 KB
最終ジャッジ日時	2023-10-12 07:45:01
合計ジャッジ時間	18,523 ms
ジャッジサーバーID （参考情報）	judge15 / judge13

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	121 ms 55,756 KB
testcase_01	AC	122 ms 55,584 KB
testcase_02	AC	120 ms 55,980 KB
testcase_03	AC	122 ms 55,764 KB
testcase_04	AC	122 ms 55,376 KB
testcase_05	AC	120 ms 55,648 KB
testcase_06	AC	122 ms 55,364 KB
testcase_07	AC	120 ms 55,668 KB
testcase_08	AC	121 ms 55,524 KB
testcase_09	AC	120 ms 55,536 KB
testcase_10	AC	121 ms 55,908 KB
testcase_11	WA	-
testcase_12	AC	121 ms 55,652 KB
testcase_13	WA	-
testcase_14	WA	-
testcase_15	AC	118 ms 55,812 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	AC	120 ms 56,084 KB
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	AC	120 ms 55,356 KB
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	AC	121 ms 56,208 KB
testcase_29	WA	-
testcase_30	WA	-
testcase_31	AC	122 ms 55,568 KB
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	AC	119 ms 55,728 KB
testcase_37	AC	121 ms 55,676 KB
testcase_38	AC	120 ms 56,272 KB
testcase_39	AC	119 ms 55,804 KB
testcase_40	AC	120 ms 55,872 KB
testcase_41	AC	122 ms 55,764 KB
testcase_42	AC	119 ms 55,776 KB
testcase_43	AC	121 ms 55,724 KB
testcase_44	AC	123 ms 55,588 KB
testcase_45	AC	121 ms 55,816 KB
testcase_46	AC	123 ms 55,672 KB
testcase_47	AC	121 ms 55,976 KB
testcase_48	AC	121 ms 57,744 KB
testcase_49	AC	122 ms 55,736 KB
testcase_50	AC	121 ms 55,880 KB
testcase_51	AC	120 ms 55,672 KB
testcase_52	AC	121 ms 55,620 KB
testcase_53	AC	122 ms 55,696 KB
testcase_54	AC	121 ms 54,144 KB
testcase_55	AC	121 ms 54,308 KB
testcase_56	AC	122 ms 55,860 KB
testcase_57	AC	121 ms 55,948 KB
testcase_58	AC	123 ms 55,412 KB
testcase_59	AC	124 ms 55,592 KB
testcase_60	AC	122 ms 55,572 KB
testcase_61	AC	123 ms 55,564 KB
testcase_62	AC	121 ms 56,036 KB
testcase_63	AC	120 ms 55,464 KB
testcase_64	AC	122 ms 55,728 KB
testcase_65	AC	120 ms 55,952 KB
testcase_66	AC	122 ms 56,732 KB
testcase_67	AC	120 ms 55,916 KB
testcase_68	AC	122 ms 55,804 KB
testcase_69	AC	120 ms 55,864 KB
testcase_70	AC	123 ms 55,416 KB
testcase_71	AC	126 ms 55,804 KB
testcase_72	AC	119 ms 56,028 KB
testcase_73	AC	123 ms 55,880 KB
testcase_74	AC	119 ms 55,884 KB
testcase_75	AC	119 ms 55,880 KB
testcase_76	AC	122 ms 55,672 KB
testcase_77	AC	119 ms 56,196 KB
testcase_78	AC	119 ms 55,904 KB
testcase_79	AC	123 ms 55,888 KB
testcase_80	AC	127 ms 56,236 KB
testcase_81	AC	125 ms 56,420 KB
testcase_82	AC	121 ms 56,064 KB
testcase_83	AC	121 ms 55,996 KB
testcase_84	AC	129 ms 56,080 KB
testcase_85	AC	119 ms 56,040 KB
testcase_86	AC	129 ms 55,728 KB
testcase_87	AC	130 ms 55,736 KB
testcase_88	AC	120 ms 55,884 KB
testcase_89	AC	119 ms 56,316 KB
testcase_90	AC	127 ms 56,096 KB
testcase_91	AC	120 ms 55,964 KB
testcase_92	AC	121 ms 55,708 KB
testcase_93	AC	124 ms 55,416 KB
testcase_94	AC	123 ms 53,744 KB
testcase_95	AC	123 ms 56,024 KB
testcase_96	AC	126 ms 56,068 KB
testcase_97	AC	124 ms 55,772 KB
testcase_98	AC	123 ms 55,644 KB
testcase_99	AC	126 ms 55,936 KB
testcase_100	AC	127 ms 56,412 KB
testcase_101	AC	139 ms 56,500 KB
testcase_102	AC	123 ms 55,876 KB
testcase_103	AC	119 ms 55,944 KB
testcase_104	AC	122 ms 56,252 KB
testcase_105	AC	119 ms 55,408 KB
testcase_106	AC	126 ms 55,680 KB

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

ソースコード

raw source code

package no308;

import java.math.BigInteger;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	public static final BigInteger EIGHT = new BigInteger("8");
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		BigInteger n = sc.nextBigInteger();
		if (n.compareTo(BigInteger.valueOf(60)) < 0) {
			System.out.println(solveNaive(n.intValue()));
			return;
		}
		if (!n.remainder(EIGHT).equals(BigInteger.ONE) || !n.subtract(EIGHT).isProbablePrime(20)) {
			System.out.println(8);
		}else{
			System.out.println(14);
		}
	}

	public static int solveNaive(int n) {
		boolean[] isPrime = isPrimeArray(n);
		for(int w=1;w<=n;w++) {
			boolean[] used = new boolean[n+1];
			Queue<Integer> q = new ArrayDeque<>();
			used[1] = true;
			q.offer(1);
			while(!q.isEmpty()) {
				int x = q.poll();
				check(x+1,n,isPrime,used,q);
				check(x-1,n,isPrime,used,q);
				check(x+w,n,isPrime,used,q);
				check(x-w,n,isPrime,used,q);
			}
			if (used[n]) {
				return w;
			}
		}
		return -1;
	}

	public static void check(int x,int n,boolean[] isPrime,boolean[] used,Queue<Integer> q) {
		if (x < 1 || x > n || isPrime[x] || used[x]) {
			return;
		}
		used[x] = true;
		q.offer(x);
	}

	public static boolean[] isPrimeArray(int max) {
		boolean[] isPrime = new boolean[max+1];
		Arrays.fill(isPrime, true);
		isPrime[0] = isPrime[1] = false;
		for(int i=2;i*i<=max;i++) {
			if (isPrime[i]) {
				int j = i * 2;
				while(j<=max) {
					isPrime[j] = false;
					j += i;
				}
			}
		}
		return isPrime;
	}

}

yukicoder

結果

テストケース

ソースコード