#145154 (Java21) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	startcpp
提出日時	2017-01-21 23:43:12
言語	Java21 (openjdk 21)
結果	AC
実行時間	213 ms / 3,000 ms
コード長	1,655 bytes
コンパイル時間	1,772 ms
コンパイル使用メモリ	75,952 KB
実行使用メモリ	40,236 KB
最終ジャッジ日時	2024-06-02 09:23:33
合計ジャッジ時間	10,349 ms
ジャッジサーバーID （参考情報）	judge3 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	46 ms 37,044 KB
testcase_01	AC	45 ms 37,168 KB
testcase_02	AC	46 ms 37,192 KB
testcase_03	AC	47 ms 36,972 KB
testcase_04	AC	44 ms 36,992 KB
testcase_05	AC	44 ms 37,012 KB
testcase_06	AC	45 ms 37,228 KB
testcase_07	AC	45 ms 37,204 KB
testcase_08	AC	46 ms 37,016 KB
testcase_09	AC	44 ms 36,748 KB
testcase_10	AC	44 ms 37,220 KB
testcase_11	AC	44 ms 36,784 KB
testcase_12	AC	45 ms 36,904 KB
testcase_13	AC	45 ms 37,220 KB
testcase_14	AC	44 ms 37,128 KB
testcase_15	AC	45 ms 37,072 KB
testcase_16	AC	45 ms 37,064 KB
testcase_17	AC	44 ms 37,212 KB
testcase_18	AC	45 ms 36,640 KB
testcase_19	AC	45 ms 37,200 KB
testcase_20	AC	46 ms 36,776 KB
testcase_21	AC	50 ms 37,024 KB
testcase_22	AC	50 ms 37,332 KB
testcase_23	AC	45 ms 36,976 KB
testcase_24	AC	47 ms 37,100 KB
testcase_25	AC	57 ms 37,460 KB
testcase_26	AC	53 ms 36,776 KB
testcase_27	AC	47 ms 36,960 KB
testcase_28	AC	47 ms 36,956 KB
testcase_29	AC	49 ms 37,180 KB
testcase_30	AC	49 ms 36,880 KB
testcase_31	AC	51 ms 36,936 KB
testcase_32	AC	58 ms 37,164 KB
testcase_33	AC	57 ms 37,328 KB
testcase_34	AC	56 ms 37,348 KB
testcase_35	AC	54 ms 37,132 KB
testcase_36	AC	53 ms 36,648 KB
testcase_37	AC	45 ms 37,096 KB
testcase_38	AC	45 ms 37,072 KB
testcase_39	AC	53 ms 37,228 KB
testcase_40	AC	51 ms 36,904 KB
testcase_41	AC	51 ms 37,220 KB
testcase_42	AC	52 ms 36,952 KB
testcase_43	AC	50 ms 36,884 KB
testcase_44	AC	49 ms 37,012 KB
testcase_45	AC	46 ms 37,052 KB
testcase_46	AC	47 ms 37,076 KB
testcase_47	AC	46 ms 37,184 KB
testcase_48	AC	70 ms 37,404 KB
testcase_49	AC	60 ms 37,164 KB
testcase_50	AC	53 ms 37,196 KB
testcase_51	AC	52 ms 37,076 KB
testcase_52	AC	48 ms 37,080 KB
testcase_53	AC	82 ms 38,212 KB
testcase_54	AC	139 ms 40,012 KB
testcase_55	AC	136 ms 39,332 KB
testcase_56	AC	138 ms 39,656 KB
testcase_57	AC	99 ms 38,824 KB
testcase_58	AC	103 ms 39,180 KB
testcase_59	AC	84 ms 38,448 KB
testcase_60	AC	86 ms 39,328 KB
testcase_61	AC	89 ms 39,320 KB
testcase_62	AC	143 ms 40,004 KB
testcase_63	AC	107 ms 39,404 KB
testcase_64	AC	94 ms 38,784 KB
testcase_65	AC	101 ms 39,344 KB
testcase_66	AC	47 ms 37,208 KB
testcase_67	AC	45 ms 37,128 KB
testcase_68	AC	137 ms 39,704 KB
testcase_69	AC	138 ms 39,668 KB
testcase_70	AC	132 ms 39,644 KB
testcase_71	AC	137 ms 39,592 KB
testcase_72	AC	109 ms 39,080 KB
testcase_73	AC	181 ms 40,064 KB
testcase_74	AC	183 ms 40,116 KB
testcase_75	AC	56 ms 37,340 KB
testcase_76	AC	139 ms 39,864 KB
testcase_77	AC	88 ms 39,084 KB
testcase_78	AC	164 ms 39,876 KB
testcase_79	AC	138 ms 39,796 KB
testcase_80	AC	156 ms 39,892 KB
testcase_81	AC	138 ms 39,756 KB
testcase_82	AC	46 ms 37,032 KB
testcase_83	AC	88 ms 38,824 KB
testcase_84	AC	96 ms 39,376 KB
testcase_85	AC	127 ms 39,664 KB
testcase_86	AC	159 ms 39,920 KB
testcase_87	AC	213 ms 40,104 KB
testcase_88	AC	209 ms 40,236 KB

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

ソースコード

raw source code

import java.io.*;

class Prime {
	boolean[] is_prime;
	int[] primes;
	
	void setPrime(int n) {
		int i, j;
		
		is_prime = new boolean[n + 1];
		is_prime[0] = false;
		is_prime[1] = false;
		for (i = 2; i <= n; i++) { is_prime[i] = true; }
		
		int cnt = 0;
		for (i = 2; i <= n; i++) {
			if (is_prime[i]) {
				for (j = i * 2; j <= n; j += i) {
					is_prime[j] = false;
				}
				cnt++;
			}
		}
		
		primes = new int[cnt];
		int id = 0;
		for (i = 2; i <= n; i++) {
			if (!is_prime[i]) continue;
			primes[id] = i;
			id++;
		}
	}
	
	int[] getPrimes() { return primes; }
	boolean isPrime(int x) { return is_prime[x]; }
};

class Solver {
	int[] cnts;
	
	public static void main(String[] args) {
		Solver solver = new Solver();
		solver.solve();
	}
	
	void solve() {
		int n = readInt();
		Prime prime = new Prime();
		prime.setPrime(3 * n);
		int[] primes = prime.getPrimes();
		initCnts(3 * n);
		
		cnts[primes[0] + primes[1]]++;
		
		long ans = 0;
		int max_exist = primes[0] + primes[1];
		for (int i = 2; i < primes.length && primes[i] <= n; i++) {
			for (int j = i + 1; j < primes.length && primes[j] - primes[i] <= max_exist; j++) {
				ans += cnts[primes[j] - primes[i]];
			}
			for (int j = 0; j < i; j++) {
				cnts[primes[i] + primes[j]]++;
			}
			max_exist = primes[i] + primes[i - 1];
		}
		
		System.out.println(ans);
	}
	
	int readInt() {
		try {
			BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
			String s = r.readLine();
			return Integer.parseInt(s);
		}
		catch (IOException e) {
			return 0;
		}
	}
	
	void initCnts(int n) {
		cnts = new int[n + 1];
		for (int i = 0; i <= n; i++) cnts[i] = 0;
	}
}

yukicoder

結果

テストケース

ソースコード