01010010011101010101

Untitled

Dec 7th, 2022
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.08 KB | None | 0 0
  1. #!/usr/bin/env python3
  2.  
  3. import time
  4. from bitarray import bitarray
  5. from typing import List
  6. from multiprocessing import Pool
  7.  
  8. PRIMES_FILE_NAME = "primes.txt"
  9.  
  10.  
  11. class Eratosthenes:
  12. def __init__(self, process: int = 0):
  13. self.process = process
  14.  
  15. @staticmethod
  16. def sequential_sieve(limit: int) -> List[int]:
  17. """
  18. Sequential version of eratosthenes sieve
  19. """
  20.  
  21. result = bitarray(limit + 1)
  22. result.setall(1)
  23. result[0] = 0
  24. result[1] = 0
  25. for value in range(2, int(limit ** 0.5) + 1):
  26. if not result[value]:
  27. continue
  28. multiple = value + value
  29. while multiple <= limit:
  30. result[multiple] = 0
  31. multiple += value
  32.  
  33. return [index for index, value in enumerate(result) if value]
  34.  
  35. @staticmethod
  36. def worker(left_bound: int, right_bound: int) -> int:
  37. """
  38. Worker executes sieving for a given range
  39. """
  40.  
  41. left_bound = max(left_bound, 2) # min value is 2
  42. print(f"worker range ({left_bound}, {right_bound})")
  43.  
  44. primes = list(map(int, open(PRIMES_FILE_NAME).read().split()))
  45. result = list(range(left_bound, right_bound))
  46. prime_limit = int(right_bound ** 0.5)
  47. for prime in primes:
  48. if prime > prime_limit:
  49. break
  50. multiple = (-left_bound) % prime
  51. if multiple + left_bound == prime:
  52. multiple += prime
  53. size = right_bound - left_bound
  54. while multiple < size:
  55. result[multiple] = 0
  56. multiple += prime
  57.  
  58. return [value for value in result if value]
  59.  
  60. def parallel_sieve(self, limit: int) -> int:
  61. """
  62. Parallel version of esrastotens sieve
  63. """
  64.  
  65. # find all primes up to sqrt(limit) and save it to file
  66. primes = self.sequential_sieve(int(limit ** 0.5))
  67. primes = ' '.join(map(str, primes))
  68.  
  69. with open(PRIMES_FILE_NAME, "w") as file_handler:
  70. file_handler.write(primes)
  71.  
  72. # parallel processing
  73. result = []
  74. with Pool(self.process) as pool:
  75. params = [(limit // self.process * x, limit // self.process * (x + 1))
  76. for x in range(self.process)]
  77. for primes in pool.starmap(Eratosthenes.worker, params):
  78. result.extend(primes)
  79.  
  80. return result
  81.  
  82. def compute(self, limit: int) -> int:
  83. """
  84. This method returns the number of found primes up to 'limit'
  85. """
  86.  
  87. # when number of processes is less than 2 do ssequential processing
  88. if self.process < 2:
  89. print("Sequential processing...")
  90. return len(self.sequential_sieve(limit))
  91.  
  92. print("Parallel processing...")
  93. return len(self.parallel_sieve(limit))
  94.  
  95.  
  96. if __name__ == "__main__":
  97. sieve = Eratosthenes(10)
  98. start = time.time()
  99. print(f"num of primes: {sieve.compute(10**8)}")
  100. stop = time.time()
  101. print(f"time: {stop-start:.02f}")
  102.  
Advertisement
Add Comment
Please, Sign In to add comment