結果

問題 No.106 素数が嫌い！2
ユーザー 👑 KazunKazun
提出日時 2020-09-15 19:09:22
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 496 ms / 5,000 ms
コード長 880 bytes
コンパイル時間 238 ms
コンパイル使用メモリ 82,468 KB
実行使用メモリ 92,488 KB
最終ジャッジ日時 2024-06-22 01:53:07
合計ジャッジ時間 4,749 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 266 ms
84,140 KB
testcase_01 AC 32 ms
52,700 KB
testcase_02 AC 31 ms
54,136 KB
testcase_03 AC 32 ms
52,464 KB
testcase_04 AC 258 ms
84,144 KB
testcase_05 AC 496 ms
92,488 KB
testcase_06 AC 485 ms
92,244 KB
testcase_07 AC 484 ms
91,712 KB
testcase_08 AC 81 ms
76,984 KB
testcase_09 AC 78 ms
77,128 KB
testcase_10 AC 489 ms
91,840 KB
testcase_11 AC 256 ms
82,944 KB
testcase_12 AC 494 ms
91,160 KB
testcase_13 AC 32 ms
52,792 KB
testcase_14 AC 32 ms
52,524 KB
testcase_15 AC 39 ms
62,224 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def Smallest_Prime_Factor(N):
    """0,1,2,...,Nの最小の素因数のリスト(0,1については1にしている)
    """

    N=abs(N)
    L=[0]*(N+1)
    L[0]=L[1]=1

    for p in range(2,N+1):
        if L[p]==0:
            for q in range(p,N+1,p):
                if L[q]==0:
                    L[q]=p

    return L

def Faster_Prime_Factorization(N,L):
    """

    L:Smallest_Prime_Factors(N)で求めたリスト
    """
    N=abs(N)
    if N<=1:
        return [N]

    D=[]
    a=L[N]
    k=0
    while N>1:
        if a==L[N]:
            k+=1
        else:
            D.append([a,k])
            a=L[N]
            k=1
        N//=L[N]

    D.append([a,1])
    return D
#================================================
N,K=map(int,input().split())
T=Smallest_Prime_Factor(N)

X=0
for i in range(2,N+1):
    X+=(len(Faster_Prime_Factorization(i,T))>=K)
print(X)
0