結果
問題 | No.144 エラトステネスのざる |
ユーザー | tonnnura172 |
提出日時 | 2020-05-06 11:49:53 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 456 ms / 2,000 ms |
コード長 | 1,161 bytes |
コンパイル時間 | 375 ms |
コンパイル使用メモリ | 87,328 KB |
実行使用メモリ | 110,160 KB |
最終ジャッジ日時 | 2023-09-10 21:14:15 |
合計ジャッジ時間 | 7,037 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 163 ms
80,304 KB |
testcase_01 | AC | 160 ms
80,380 KB |
testcase_02 | AC | 165 ms
80,520 KB |
testcase_03 | AC | 163 ms
80,492 KB |
testcase_04 | AC | 163 ms
80,320 KB |
testcase_05 | AC | 165 ms
80,196 KB |
testcase_06 | AC | 171 ms
81,092 KB |
testcase_07 | AC | 169 ms
81,372 KB |
testcase_08 | AC | 168 ms
81,392 KB |
testcase_09 | AC | 171 ms
81,176 KB |
testcase_10 | AC | 169 ms
81,540 KB |
testcase_11 | AC | 164 ms
81,152 KB |
testcase_12 | AC | 169 ms
81,436 KB |
testcase_13 | AC | 405 ms
110,036 KB |
testcase_14 | AC | 410 ms
109,828 KB |
testcase_15 | AC | 428 ms
110,160 KB |
testcase_16 | AC | 431 ms
109,888 KB |
testcase_17 | AC | 420 ms
109,688 KB |
testcase_18 | AC | 456 ms
109,948 KB |
testcase_19 | AC | 409 ms
109,896 KB |
ソースコード
import sys, re from collections import deque, defaultdict, Counter from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd, log from itertools import accumulate, permutations, combinations, product from operator import itemgetter, mul, add from copy import deepcopy from string import ascii_lowercase, ascii_uppercase, digits from bisect import bisect, bisect_left from heapq import heappush, heappop from functools import reduce, lru_cache def input(): return sys.stdin.readline().strip() def INT(): return int(input()) def MAP(): return map(int, input().split()) def LIST(): return list(map(int, input().split())) def ZIP(n): return zip(*(MAP() for _ in range(n))) sys.setrecursionlimit(10 ** 9) INF = float('inf') mod = 10 ** 9 + 7 def sieve(n): s = [True] * n for x in range(2, int(n ** 0.5) + 1): if s[x]: for i in range(x + x, n, x): s[i] = False return [i for i in range(n) if s[i] and i > 1] N, p = [c(x) for c, x in zip([int, float], input().split())] ans = 0 primes = sieve(N+1) cnt = [1]*(N+1) cnt[0], cnt[1] = 0, 0 for n in range(2, N+1): tmp = 2 while n*tmp <= N: cnt[n*tmp] *= (1-p) tmp += 1 print(sum(cnt))