""" We always are confused about which is_prime logic is best. But no worries, I've figured out the best and worst for you. I took the best 17 I could find and measured their time for variety of numbers. Just copy any function and try it out. Check out all the functions because logic for each is brilliant. Best: 1. 2 2. 14 3. 5 4. 3 (For large numbers | > 350,000) 4. 15 (For small numbers | < 350,000) Worst: 1. 12 - Limited to few 1000s due to recursion limits 2. 8, 13 - Extremely slow 3. 7, 10 - Too slow 4. 9, 14 - Slow Links for reference: # https://stackoverflow.com/questions/15285534/isprime-function-for-python-language # https://www.geeksforgeeks.org/prime-functions-python-sympy/ # Func 13 explanation - http://montreal.pm.org/tech/neil_kandalgaonkar.shtml """ def is_prime1(n): for i in range(2,int(n**0.5)+1): if n%i==0: return False return True def is_prime2(n): if n == 2 or n == 3: return True if n < 2 or n%2 == 0: return False if n < 9: return True if n%3 == 0: return False r = int(n**0.5) f = 5 while f <= r: if n%f == 0: return False if n%(f+2) == 0: return False f +=6 return True def is_prime3(n): if n==2 or n==3: return True if n%2==0 or n<2: return False for i in range(3,int(n**0.5)+1,2): # only odd numbers if n%i==0: return False return True def is_prime4(n): return 2 in [n,2**n%n] def is_prime5(n): import sympy return sympy.isprime(n) def is_prime6(n): """ pre-condition: n is a nonnegative integ post-condition: return True if n is prime""" if n < 2: return False if n % 2 == 0: return n == 2 # return False k = 3 while k*k <= n: if n % k == 0: return False k += 2 return True def is_prime7(x): if x < 2: return False elif x == 2: return True for n in range( 2, x): if x % n == 0: return False return True def is_prime8(x): from math import factorial return factorial(x - 1) % x == x - 1 is_prime9 = lambda x: all(x % i != 0 for i in range(int(x** 0.5)+1 )[2:]) def is_prime10(x): if x < 2: return False for n in range(2, (x) - 1): if x % n == 0 : return False return True def is_prime11(n): '''Returns True if n is prime, False if n is not prime. Will not work if n is 0''' import math # Make sure n is a positive integer n = abs(int(n)) # Case 1: the number is 2 (prime) if n == 2: return True # Case 2: the number is even (not prime) if n % 2 == 0: return False # Case 3: the number is odd (could be prime or not) # Check odd numbers less than the square root for possible factors r = math.sqrt(n) x = 3 while x <= r: if n % x == 0: return False # A factor was found, so number is not prime x += 2 # Increment to the next odd number # No factors found, so number is prime return True def is_prime12(num,div=2): if(num==div): return True elif(num % div == 0): return False else: return is_prime12(num,div+ 1) def is_prime13(n): import re return not re.match(r'^1?$|^(11+?)\1+$' ,n*'1') def is_prime14(N): if N>1: from random import randint for _ in range(5): Num = randint(1, N-1) if pow( Num,N- 1,N)!=1: return False return True return False def is_prime15(n): # Corner Cases if (n<= 1): return False elif (n<= 3): return True elif (n% 2 == 0 or n%3 == 0): return False i = 5 while i*i<=n: if (n%i== 0 or n%(i+2)== 0): return False i += 6 return True def is_prime16(n): if n<2: return(0) if n==2 or n==3: return(n) from math import sqrt lpend = int(sqrt(n))+1 for i in range(2, lpend): if n%i == 0: return(0) else: pass return(n) def isprime(n): ''' Tests if n is a prime number''' if n<2: return(0) if n==2 or n==3: return(n) if n==5 or n==7: return(n) if (n > 2) and (n%2 == 0): return 0 if (n > 3) and (n%3 == 0): return 0 if (n > 5) and (n%5 == 0): return 0 if (n > 7) and (n%7 == 0): return 0 from math import sqrt lpend = int(sqrt(n))+1 for i in range(2, lpend): if n%i == 0: return(0) else: pass return(n)

best_is_prime_function