anonymous / Primes.py
Created

Embed URL

HTTPS clone URL

SSH clone URL

You can clone with HTTPS or SSH.

Download Gist

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

View Primes.py
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.