#288937 (Python3) No.732 3PrimeCounting

提出ソース

結果

問題	No.732 3PrimeCounting
ユーザー	togetogehat
提出日時	2018-10-02 08:20:07
言語	Python3 (3.12.2 + numpy 1.26.4 + scipy 1.12.0)
結果	AC
実行時間	1,770 ms / 3,000 ms
コード長	369 bytes
コンパイル時間	225 ms
コンパイル使用メモリ	12,672 KB
実行使用メモリ	45,484 KB
最終ジャッジ日時	2024-10-12 10:01:37
合計ジャッジ時間	65,478 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	510 ms 43,940 KB
testcase_01	AC	510 ms 44,328 KB
testcase_02	AC	514 ms 44,200 KB
testcase_03	AC	507 ms 44,068 KB
testcase_04	AC	512 ms 44,196 KB
testcase_05	AC	510 ms 44,080 KB
testcase_06	AC	510 ms 44,452 KB
testcase_07	AC	510 ms 43,940 KB
testcase_08	AC	516 ms 43,940 KB
testcase_09	AC	506 ms 43,816 KB
testcase_10	AC	515 ms 44,192 KB
testcase_11	AC	505 ms 43,944 KB
testcase_12	AC	513 ms 44,200 KB
testcase_13	AC	511 ms 44,208 KB
testcase_14	AC	512 ms 44,196 KB
testcase_15	AC	509 ms 44,208 KB
testcase_16	AC	505 ms 44,192 KB
testcase_17	AC	510 ms 43,944 KB
testcase_18	AC	504 ms 43,944 KB
testcase_19	AC	507 ms 44,204 KB
testcase_20	AC	515 ms 44,328 KB
testcase_21	AC	519 ms 43,948 KB
testcase_22	AC	522 ms 44,328 KB
testcase_23	AC	508 ms 43,816 KB
testcase_24	AC	508 ms 44,200 KB
testcase_25	AC	521 ms 43,944 KB
testcase_26	AC	520 ms 43,948 KB
testcase_27	AC	521 ms 44,140 KB
testcase_28	AC	507 ms 43,944 KB
testcase_29	AC	516 ms 44,200 KB
testcase_30	AC	511 ms 44,328 KB
testcase_31	AC	511 ms 44,076 KB
testcase_32	AC	511 ms 43,944 KB
testcase_33	AC	520 ms 44,068 KB
testcase_34	AC	517 ms 43,812 KB
testcase_35	AC	516 ms 43,944 KB
testcase_36	AC	509 ms 44,048 KB
testcase_37	AC	502 ms 43,948 KB
testcase_38	AC	509 ms 44,200 KB
testcase_39	AC	517 ms 44,204 KB
testcase_40	AC	519 ms 43,812 KB
testcase_41	AC	516 ms 43,808 KB
testcase_42	AC	520 ms 44,200 KB
testcase_43	AC	520 ms 44,328 KB
testcase_44	AC	511 ms 44,304 KB
testcase_45	AC	512 ms 44,080 KB
testcase_46	AC	511 ms 43,932 KB
testcase_47	AC	507 ms 44,332 KB
testcase_48	AC	527 ms 44,068 KB
testcase_49	AC	520 ms 44,068 KB
testcase_50	AC	521 ms 43,824 KB
testcase_51	AC	529 ms 43,940 KB
testcase_52	AC	514 ms 44,456 KB
testcase_53	AC	547 ms 43,940 KB
testcase_54	AC	1,045 ms 44,080 KB
testcase_55	AC	1,024 ms 43,816 KB
testcase_56	AC	1,062 ms 44,076 KB
testcase_57	AC	603 ms 44,196 KB
testcase_58	AC	591 ms 43,940 KB
testcase_59	AC	539 ms 43,816 KB
testcase_60	AC	636 ms 44,324 KB
testcase_61	AC	638 ms 43,948 KB
testcase_62	AC	1,037 ms 45,092 KB
testcase_63	AC	773 ms 43,816 KB
testcase_64	AC	688 ms 43,948 KB
testcase_65	AC	685 ms 44,452 KB
testcase_66	AC	553 ms 44,456 KB
testcase_67	AC	554 ms 44,320 KB
testcase_68	AC	1,139 ms 43,812 KB
testcase_69	AC	1,120 ms 44,072 KB
testcase_70	AC	1,038 ms 43,944 KB
testcase_71	AC	1,074 ms 44,320 KB
testcase_72	AC	766 ms 44,332 KB
testcase_73	AC	1,394 ms 45,356 KB
testcase_74	AC	1,373 ms 45,480 KB
testcase_75	AC	512 ms 44,072 KB
testcase_76	AC	1,096 ms 44,200 KB
testcase_77	AC	603 ms 43,936 KB
testcase_78	AC	1,181 ms 44,708 KB
testcase_79	AC	1,135 ms 44,200 KB
testcase_80	AC	1,093 ms 44,964 KB
testcase_81	AC	1,032 ms 43,948 KB
testcase_82	AC	513 ms 44,204 KB
testcase_83	AC	596 ms 44,204 KB
testcase_84	AC	611 ms 44,200 KB
testcase_85	AC	964 ms 43,808 KB
testcase_86	AC	1,124 ms 44,976 KB
testcase_87	AC	1,770 ms 45,484 KB
testcase_88	AC	1,758 ms 45,092 KB

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

ソースコード

raw source code

import numpy as np
n = int(input())
sieve = np.ones(n*3+1, dtype=bool)
for i in range(2, int((n*3)**0.5)+2):
    if sieve[i]:
        sieve[i+i::i] = False
ps1 = np.where(sieve)[0][2:]
ps2 = ps1[ps1 <= n]
cnt = np.zeros(n*3+1, dtype='int64')
res = 0
for i in reversed(range(len(ps2))):
    a = ps2[i]
    res += cnt[ps1 - a].sum()
    cnt[ps2[i+1:] + a] += 1
print(res)

yukicoder

結果

テストケース

ソースコード