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