#!/usr/bin/python
def make_offsets(primes):
'''
`primes` MUST be a list of all primes from 2 to stop.
All primes except 2 and 3 are 6n - 1 or 6n + 1 because
2*3 = 6 (the period) and 6n+1 and 6n-1 are the only possible
primes when n > 0.
This function extends this beyond just 2, 3, 6n+1 and 6n+5.
Returns: period, offsets
Notice: `offsets` will include 1 and will not include any prime
in `primes`. Exceptions need to be made when n == 0.
Example
=======
>>> period, offsets = table(2, 3, 5)
>>> period
30
>>> offsets
[1, 7, 11, 13, 17, 19, 23, 29]
'''
# Calculate the period.
period = 1
for p in primes:
period *= p
# Calculate valid offsets
offsets = []
i = 0
while i < period:
if all(map(lambda x: i%x, primes)):
offsets.append(i)
i += 1
# Done.
return period, offsets
def factorise(num):
'''
Return a list of (prime, power).
'''
# Handle bad values of `num`.
factors = []
if num != int(num):
raise TypeError('`num` MUST be an integer.')
elif num < -1:
factors.append((-1, 1))
num = -num
elif num == -1:
return [(-1, 1)]
elif num == 0:
return [(0, 1)]
elif num == 1:
return [(1, 1)]
# There is no need to only use primes here.
# Consider this example: 2, 3, 4, 5
# There will be no 4s because the 2s have already been
# divided away.
#
# Checking whether or not the number is a prime will take
# a longer time than realising it won't divide `num`, so
# why bother?
#
# The "only" thing that could make this faster is to not use
# so damn many composite numbers in the first place, that's
# where the `make_offsets` function comes to use.
#
# Use the `make_offsets` function to exclude some composite numbers.
# Primes are {2, 3, 5} when n == 0 and {6n+1, 6n+5} when n > 0
# Extend this beyond just 2*3, go to 2*3*5*7*11*13*17
#
#global primes # Won't be modified, global declarations only
#global period # here for clarity.
#global offsets
table = primes + offsets[1:] # Offset table to use when n == 0.
n_times_period = 0 # n alone is only needed for checking if n is
# zero or not.
sqrt_num = num**0.5 # If the potential divident > sqrt(num) then
# there must have been a previous divident, but
# there wasn't. Therefore`, `num` must be prime.
# Can't handle num == 1 properly.
while num > 1:
for offset in table:
divident = n_times_period + offset
# Check if `num` is prime.
if divident > sqrt_num:
factors.append((num, 1))
num = 1
break
# Divide away the selected factor.
power = 0
while num % divident == 0:
power += 1
num /= divident
if power:
factors.append((divident, power))
# `num` does not magically become 1 -> continue in same block.
if num == 1:
break
# `num` has changed, change `sqrt_num`
sqrt_num = num**0.5
# Offset table to use when n > 0.
# Change only once.
if n_times_period == 0:
table = offsets
# Next iteration:
n_times_period += period
return factors
def main():
import sys
try:
while True:
# Get input
sys.stderr.write('\nEnter number to factorise: ')
sys.stderr.flush()
line = sys.stdin.readline()
if not line:
break
if line == '\n':
# Shut up.
continue
# Parse input
try:
num = int(line)
except ValueError as e:
sys.stderr.write(str(e) + '\n')
continue
# Compute input
try:
factors = factorise(num)
except ValueError as e:
sys.stderr.write(str(e) + '\n')
continue
# Print out.
s = ' * '.join(map(lambda x: '{}**{}'.format(*x), factors))
sys.stdout.write('{} = {}\n'.format(num, s))
except KeyboardInterrupt:
pass
sys.stderr.write('\n')
# Pre-initialize the offsets table.
primes = [2, 3, 5, 7, 11, 13, 17] # Becomes slow at 19.
period, offsets = make_offsets(primes)
if __name__ == '__main__':
main()