44 lines
1.1 KiB
Python
44 lines
1.1 KiB
Python
"""
|
||
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
|
||
What is the 10001st prime number?
|
||
"""
|
||
|
||
import time
|
||
from math import log
|
||
|
||
|
||
def timer(func):
|
||
def wrapper(*args, **kwargs):
|
||
start = time.time()
|
||
result = func(*args, **kwargs)
|
||
end = time.time()
|
||
print(f"{func.__name__} took {end - start:.6f} seconds")
|
||
return result
|
||
|
||
return wrapper
|
||
|
||
|
||
@timer
|
||
def sieve_nth_prime(n: int) -> int | None:
|
||
if n == 1:
|
||
return 2
|
||
# 估算上限：第n个质数约在 n*log(n) 附近
|
||
limit = int(n * (log(n) + log(log(n)))) + 10 if n > 6 else 20
|
||
sieve = [True] * limit
|
||
sieve[0:2] = [False, False] # 0和1不是质数
|
||
|
||
count = 0
|
||
for p in range(2, limit):
|
||
if sieve[p]:
|
||
count += 1
|
||
if count == n:
|
||
return p
|
||
# 标记倍数
|
||
sieve[p * p : limit : p] = [False] * ((limit - 1 - p * p) // p + 1)
|
||
|
||
return None
|
||
|
||
|
||
if __name__ == "__main__":
|
||
print(sieve_nth_prime(10001))
|