Create a gist now

Instantly share code, notes, and snippets.

anonymous /Primes.py
Created Feb 15, 2013

Filters non-prime numbers in Python when working with large data sets.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment