public
anonymous / Primes.py
Created

Filters non-prime numbers in Python when working with large data sets.

  • Download Gist
Primes.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
def next_down(number):
number -=1
for i in range(3): #there will be a max of three iterations here (6,5,4)
if number %2 == 0 or number %5 == 0:
number -=1
else:
break
return number
 
def sum_digits(numstr):
sum = 0
for digit in numstr:
sum += int(digit)
return sum
 
def last_two_digits(numstr):
return int(numstr[-2:])
 
def last_three_digits(numstr):
return int(numstr[-3:])
 
def seven_test(numstr):
last_digit = numstr[-1]
double = int(last_digit)*2
is_divis = int(numstr[:-1])-double
rem = is_divis % 7
return (rem == 0) or (is_divis == 0)
 
def eleven_test(numstr):
part_one = int(numstr[1])
part_two = int(numstr[0])
i = 2
while i < len(numstr):
if i % 2 ==0:
part_two += int(numstr[i])
else:
part_one += int(numstr[i])
i+=1
diff = part_one - part_two
if (diff == 0) or (diff % 11 == 0):
return True
 
def thirteen_test(numstr):
last_digit = int(numstr[-1])
all_but_last = int(numstr[:-1])
nine_x = last_digit*9
return (all_but_last - nine_x) % 13 == 0
 
def worth_testing(num):
as_str = str(num)
# Divis by 5, 10
if as_str.endswith('5'):
return False
 
# Divis by 3
if sum_digits(as_str) % 3 == 0:
return False
 
# Divis by 7
if seven_test(as_str):
return False
 
# Divis by 9
if sum_digits(as_str) % 9 == 0:
return False
 
# Divis by 11
if eleven_test(as_str):
return False
 
# Divis by 13
if thirteen_test(as_str):
return False
return True
 
def is_prime(number):
# Filters out numbers divisibly by
# 1-13
sqrt = math.sqrt(number)
if (sqrt % 1.0 == 0.0):
return False
if not worth_testing(number):
return False
# If a number has a whole square root,
# it is not prime
 
iter_factor = math.ceil(sqrt)
 
# We only need to test for numbers less than
# the square root that are prime
test_numbers = primes_less_than(iter_factor)
 
for num in test_numbers:
if (number % num ==0):
return False
 
return True

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.