Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Check If A Number Is Prime
- # by Mike Kerry - Revisited July 2021 - acclivity2@gmail.com
- import time
- def checkPrime(number):
- if number < 4:
- return number > 1 # 2 and 3 return True, 0, 1 and all negative numbers return False
- if number % 6 not in (1, 5): # Any prime > 3, divided by 6 gives a remainder of 1 or 5
- return False
- # Compute 1 plus the square root of the number to be tested. This will be the largest divisor we need to consider
- sqrt = 1 + int(number ** 0.5)
- # Test the remainder for each division of divisors up to the square root
- # We start at 5 and only need to go up to the square root of number, and only in steps of 2
- for divisor in range(5, sqrt, 2):
- if not number % divisor:
- return False
- return True
- aa = [1, 2, 3, 4, 5, 6, 7, 8, 9, 100, 101, 120, 121, 127, 131, 163, 12345, 54321, 987654323]
- for a in aa:
- print(str(a).ljust(12), checkPrime(a))
- # Find the one-millionth prime number. Measure the execution time
- st = time.time()
- a, b = -1, 0
- while b < 1000000:
- a += 1
- b += checkPrime(a)
- print(a, (time.time() - st))
- # RESULTS
- # 1 False
- # 2 True
- # 3 True
- # 4 False
- # 5 True
- # 6 False
- # 7 True
- # 8 False
- # 9 False
- # 100 False
- # 101 True
- # 120 False
- # 121 False
- # 131 True
- # 127 True
- # 163 True
- # 12345 False
- # 54321 False
- # 987654323 True
- # 15485863 this is the one-millionth prime number, computed in 284 seconds (i7-2670QM processor)
Add Comment
Please, Sign In to add comment