fork(2) download
copy 
  1. import time
  2. import math
  3.  
  4.  
  5. def funclog(func):
  6.  
  7.     def wrapper(*args, **kwargs):
  8.         print(f"{func.__name__} start", *args)
  9.         start_time = time.perf_counter()
  10.         return_val = func(*args, **kwargs)
  11.         end_time = time.perf_counter()
  12.         print(f"{func.__name__} end (time={end_time-start_time:.4f})")
  13.         return return_val
  14.  
  15.     return wrapper
  16.  
  17.  
  18. def list_primes(limit):
  19.     primes = []
  20.     primes.append(2)
  21.     primes.append(3)
  22.     primes.append(5)
  23.     is_prime = [True] * (limit + 1)
  24.     is_prime[0] = False
  25.     is_prime[1] = False
  26.     inc = [6, 4, 2, 4, 2, 4, 6, 2]
  27.     p = 1
  28.     for i in range(0, limit + 1):
  29.         p += inc[i&7]
  30.         if p >= limit:
  31.             break
  32.         if is_prime[p]:
  33.             primes.append(p)
  34.             for i in range(p * p, limit + 1, p):
  35.                 is_prime[i] = False
  36.     return primes
  37.  
  38.  
  39. @funclog
  40. def P_n_2(n):
  41.     limit = max(100, n * math.log(n) * 1.2 + 2)
  42.     while True:
  43.         primes = list_primes(int(limit))
  44.         if len(primes) > n:
  45.             return primes[n - 1]
  46.         limit *= 1.2
  47.  
  48.  
  49. @funclog
  50. def P_n(n):
  51.     primes = [2]
  52.     a = b = 3
  53.     while len(primes) < n:
  54.         for i in primes:
  55.             if a % i == 0:
  56.                 b = a / i
  57.                 break
  58.         if b == a:
  59.             primes.append(a)
  60.         a += 2
  61.         b = a
  62.     return primes[n - 1]
  63.  
  64.  
  65. print(P_n(10), '\n')
  66. print(P_n(100), '\n')
  67. print(P_n(1000), '\n')
  68. print(P_n(10000), '\n')
  69.  
  70. print(P_n_2(10), '\n')
  71. print(P_n_2(100), '\n')
  72. print(P_n_2(1000), '\n')
  73. print(P_n_2(10000), '\n')
  74. print(P_n_2(100000), '\n')
  75. print(P_n_2(1000000), '\n')
Success #stdin #stdout 6.56s 181372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
P_n start 10
P_n end (time=0.0000)
29 

P_n start 100
P_n end (time=0.0006)
541 

P_n start 1000
P_n end (time=0.0524)
7919 

P_n start 10000
P_n end (time=3.3367)
104729 

P_n_2 start 10
P_n_2 end (time=0.0001)
29 

P_n_2 start 100
P_n_2 end (time=0.0001)
541 

P_n_2 start 1000
P_n_2 end (time=0.0008)
7919 

P_n_2 start 10000
P_n_2 end (time=0.0121)
104729 

P_n_2 start 100000
P_n_2 end (time=0.2122)
1299709 

P_n_2 start 1000000
P_n_2 end (time=2.9482)
15485863
https://ideone.com/3TGr00
N番目の素数
language:
Python 3 (python  3.12)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!