acclivity

pyPrimeChecker - Revised

Jan 21st, 2021 (edited)
318
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.66 KB | None | 0 0
  1. # Check If A Number Is Prime
  2. # by Mike Kerry - Revisited July 2021 - acclivity2@gmail.com
  3. import time
  4.  
  5. def checkPrime(number):
  6.     if number < 4:
  7.         return number > 1               # 2 and 3 return True, 0, 1 and all negative numbers return False
  8.     if number % 6 not in (1, 5):        # Any prime > 3, divided by 6 gives a remainder of 1 or 5
  9.         return False
  10.     # Compute 1 plus the square root of the number to be tested. This will be the largest divisor we need to consider
  11.     sqrt = 1 + int(number ** 0.5)
  12.  
  13.     # Test the remainder for each division of divisors up to the square root
  14.     # We start at 5 and only need to go up to the square root of number, and only in steps of 2
  15.     for divisor in range(5, sqrt, 2):
  16.         if not number % divisor:
  17.             return False
  18.     return True
  19.  
  20.  
  21. aa = [1, 2, 3, 4, 5, 6, 7, 8, 9, 100, 101, 120, 121, 127, 131, 163, 12345, 54321, 987654323]
  22. for a in aa:
  23.     print(str(a).ljust(12), checkPrime(a))
  24.  
  25.  
  26. # Find the one-millionth prime number. Measure the execution time
  27. st = time.time()
  28. a, b = -1, 0
  29. while b < 1000000:
  30.     a += 1
  31.     b += checkPrime(a)
  32.  
  33. print(a, (time.time() - st))
  34.  
  35. # RESULTS
  36. # 1            False
  37. # 2            True
  38. # 3            True
  39. # 4            False
  40. # 5            True
  41. # 6            False
  42. # 7            True
  43. # 8            False
  44. # 9            False
  45. # 100          False
  46. # 101          True
  47. # 120          False
  48. # 121          False
  49. # 131          True
  50. # 127          True
  51. # 163          True
  52. # 12345        False
  53. # 54321        False
  54. # 987654323    True
  55.  
  56. # 15485863     this is the one-millionth prime number, computed in 284 seconds (i7-2670QM processor)
  57.  
  58.  
  59.  
Add Comment
Please, Sign In to add comment