結果
問題 |
No.2750 Number of Prime Factors
|
ユーザー |
|
提出日時 | 2024-05-16 10:26:05 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 76 ms / 2,000 ms |
コード長 | 1,151 bytes |
コンパイル時間 | 196 ms |
コンパイル使用メモリ | 82,920 KB |
実行使用メモリ | 69,564 KB |
最終ジャッジ日時 | 2024-12-20 10:49:03 |
合計ジャッジ時間 | 2,457 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 |
ソースコード
from itertools import combinations, count, accumulate, product from typing import List from math import ceil, sqrt from collections import defaultdict def main(): N = int(input()) primes = list(calc_prime_numbers(1000)) max_prime = 1 idx = 0 while max_prime * primes[idx] <= N: max_prime *= primes[idx] idx += 1 print(idx) def calc_prime_numbers(upper: int) -> List[int]: if upper < 2: return [] if upper == 3: return [2] if upper == 4: return [2, 3] if 5 <= upper <= 6: return [2, 3, 5] if 7 <= upper <= 10: return [2, 3, 5, 7] sqrt_upper = ceil(sqrt(upper)) primes = [] prime_flag = [False, True] * (upper // 2 + 1) prime_flag[1] = False prime_flag[2] = True for num in range(3, len(prime_flag)): if not prime_flag[num]: continue if num * 2 >= len(prime_flag): continue for multi_num in range(num * 2, len(prime_flag), num): prime_flag[multi_num] = False return (num for num, flag in enumerate(prime_flag) if flag) if __name__ == "__main__": main()