結果

問題 No.3079 アルベド
ユーザー hiro1729hiro1729
提出日時 2023-12-30 10:39:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 263 ms / 2,000 ms
コード長 2,643 bytes
コンパイル時間 243 ms
コンパイル使用メモリ 81,700 KB
実行使用メモリ 78,352 KB
最終ジャッジ日時 2023-12-30 10:39:26
合計ジャッジ時間 3,091 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 107 ms
78,348 KB
testcase_01 AC 263 ms
78,352 KB
testcase_02 AC 193 ms
78,352 KB
testcase_03 AC 161 ms
78,352 KB
testcase_04 AC 223 ms
78,352 KB
testcase_05 AC 185 ms
78,348 KB
testcase_06 AC 209 ms
78,352 KB
testcase_07 AC 104 ms
78,352 KB
testcase_08 AC 114 ms
78,352 KB
testcase_09 AC 211 ms
78,352 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import gcd, isqrt

# N≦2^64で素数判定
def is_prime(N: int) -> bool:
	if N <= 1:
		return False
	if N == 2:
		return True
	if N & 1 == 0:
		return False
	s = 0
	d = N - 1
	while d & 1 == 0:
		s += 1
		d >>= 1
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		if a % N == 0:
			return True
		x = pow(a, d, N)
		if x != 1:
			t = 0
			while t < s and x < N - 1:
				t += 1
				x = x * x % N
			if t == s:
				return False
	return True

# N以下の最大の素数を返す
def biggest_prime(N: int) -> int:
	while not is_prime(N):
		N -= 1
	return N

# N以上の最小の素数を返す
def smallest_prime(N: int) -> int:
	while not is_prime(N):
		N += 1
	return N

# エラトステネスの篩 [1, N]
def Eratosthenes_Sieve(N: int) -> list:
	if N < 2:
		return []
	p = [True] * (N + 1)
	p[0] = p[1] = False
	for i in range(2, N + 1):
		if i * i > N:
			break
		if p[i]:
			for j in range(2 * i, N + 1, i):
				p[j] = False
	return p

# エラトステネスの区間篩 [A, B]
def Eratosthenes_Sieve2(A: int, B: int) -> list:
	p = [True] * (B - A + 1)
	for i in range(2, B + 1):
		if i * i > B:
			break
		if i < A:
			for j in range((A + i - 1) // i * i, B + 1, i):
				p[j - A] = False
		elif p[i - A]:
			for j in range(2 * i, B + 1, i):
				p[j - A] = False
	return p

# 約数(ソートする)
def divisor(N: int) -> list:
	d = []
	d2 = []
	for i in range(1, N + 1):
		if i * i > N:
			break
		if N % i == 0:
			d.append(i)
			if i * i < N:
				d2.append(N // i)
	return d + d2[::-1]

# 素因数分解
def factorize(N: int) -> list:
	c = 0
	while N & 1 == 0:
		c += 1
		N >>= 1
	ans = [2] * c
	while N > 1:
		n = N
		while not is_prime(n):
			m = int(n ** 0.125) + 1
			for c in range(1, n):
				y = 0
				g = 1
				q = 1
				r = 1
				while g == 1:
					x = y
					for _ in range(r >> 1, (3 * r) >> 2):
						y = (y * y + c) % n
					for k in range((3 * r) >> 2, r, m):
						ys = y
						for _ in range(min(m, r - k)):
							y = (y * y + c) % n
							q = q * (x - y) % n
						g = gcd(q, n)
						if g != 1:
							break
					r <<= 1
				if g == n:
					g = 1
					y = ys
					while g == 1:
						y = (y * y + c) % n
						g = gcd(x - y, n)
				if g != n:
					break
			n = g
		c = 0
		while N % n == 0:
			c += 1
			N //= n
		ans += [n] * c
	ans.sort()
	return ans

# ⌊N/1⌋...⌊N/N⌋をソートして返す
def quotients(N: int) -> list:
	s = isqrt(N)
	ans = [N // i for i in range(1, s + 1)]
	ans += list(range(s - (ans[-1] == s), 0, -1))
	ans.reverse()
	return ans

e = Eratosthenes_Sieve(100000)
for i in range(100000):
	e[i + 1] += e[i]
for _ in range(int(input())):
	print(e[int(input())])
0