Factorise

Simple Python module for prime factorisation. Uses the 6n plus/minus 1 phenomenom. Reasonably fast.

 Last modified 2016-10-17 Lines 162 Indexable Yes

Quick links: factorise main make_offsets

1. #!/usr/bin/python
2. def make_offsets(primes):
3.     '''
4.     `primes` MUST be a list of all primes from 2 to stop.
5.
6.     All primes except 2 and 3 are 6n - 1 or 6n + 1 because
7.     2*3 = 6 (the period) and 6n+1 and 6n-1 are the only possible
8.     primes when n > 0.
9.
10.     This function extends this beyond just 2, 3, 6n+1 and 6n+5.
11.
12.     Returns: period, offsets
13.
14.     Notice: `offsets` will include 1 and will not include any prime
15.     in `primes`.  Exceptions need to be made when n == 0.
16.
17.     Example
18.     =======
19.
20.         >>> period, offsets = table(2, 3, 5)
21.         >>> period
22.         30
23.         >>> offsets
24.         [1, 7, 11, 13, 17, 19, 23, 29]
25.     '''
26.     # Calculate the period.
27.     period = 1
28.     for p in primes:
29.         period *= p
30.     # Calculate valid offsets
31.     offsets = []
32.     i = 0
33.     while i < period:
34.         if all(map(lambda x: i%x, primes)):
35.             offsets.append(i)
36.         i += 1
37.     # Done.
38.     return period, offsets
39. def factorise(num):
40.     '''
41.     Return a list of (prime, power).
42.     '''
43.     # Handle bad values of `num`.
44.     factors = []
45.     if num != int(num):
46.         raise TypeError('`num` MUST be an integer.')
47.     elif num < -1:
48.         factors.append((-1, 1))
49.         num = -num
50.     elif num == -1:
51.         return [(-1, 1)]
52.     elif num == 0:
53.         return [(0, 1)]
54.     elif num == 1:
55.         return [(1, 1)]
56.
57.     # There is no need to only use primes here.
58.     # Consider this example: 2, 3, 4, 5
59.     # There will be no 4s because the 2s have already been
60.     # divided away.
61.     #
62.     # Checking whether or not the number is a prime will take
63.     # a longer time than realising it won't divide `num`, so
64.     # why bother?
65.     #
66.     # The "only" thing that could make this faster is to not use
67.     # so damn many composite numbers in the first place, that's
68.     # where the `make_offsets` function comes to use.
69.     #
70.     # Use the `make_offsets` function to exclude some composite numbers.
71.     # Primes are {2, 3, 5} when n == 0 and {6n+1, 6n+5} when n > 0
72.     # Extend this beyond just 2*3, go to 2*3*5*7*11*13*17
73.     #
74.     #global primes      # Won't be modified, global declarations only
75.     #global period      # here for clarity.
76.     #global offsets
77.
78.     table = primes + offsets[1:]    # Offset table to use when n == 0.
79.
80.     n_times_period = 0      # n alone is only needed for checking if n is
81.                             # zero or not.
82.
83.     sqrt_num = num**0.5     # If the potential divident > sqrt(num) then
84.                             # there must have been a previous divident, but
85.                             # there wasn't. Therefore`, `num` must be prime.
86.
87.     # Can't handle num == 1 properly.
88.     while num > 1:
89.         for offset in table:
90.             divident = n_times_period + offset
91.             # Check if `num` is prime.
92.             if divident > sqrt_num:
93.                 factors.append((num, 1))
94.                 num = 1
95.                 break
96.             # Divide away the selected factor.
97.             power = 0
98.             while num % divident == 0:
99.                 power += 1
100.                 num /= divident
101.             if power:
102.                 factors.append((divident, power))
103.                 # `num` does not magically become 1 -> continue in same block.
104.                 if num == 1:
105.                     break
106.                 # `num` has changed, change `sqrt_num`
107.                 sqrt_num = num**0.5
108.         # Offset table to use when n > 0.
109.         # Change only once.
110.         if n_times_period == 0:
111.             table = offsets
112.         # Next iteration:
113.         n_times_period += period
114.
115.     return factors
116. def main():
117.     import sys
118.     try:
119.         while True:
120.             # Get input
121.             sys.stderr.write('\nEnter number to factorise: ')
122.             sys.stderr.flush()
123.             line = sys.stdin.readline()
124.             if not line:
125.                 break
126.             if line == '\n':
127.                 # Shut up.
128.                 continue
129.             # Parse input
130.             try:
131.                 num = int(line)
132.             except ValueError as e:
133.                 sys.stderr.write(str(e) + '\n')
134.                 continue
135.             # Compute input
136.             try:
137.                 factors = factorise(num)
138.             except ValueError as e:
139.                 sys.stderr.write(str(e) + '\n')
140.                 continue
141.             # Print out.
142.             s = ' * '.join(map(lambda x: '{}**{}'.format(*x), factors))
143.             sys.stdout.write('{} = {}\n'.format(num, s))
144.     except KeyboardInterrupt:
145.         pass
146.     sys.stderr.write('\n')
147. # Pre-initialize the offsets table.
148. primes = [2, 3, 5, 7, 11, 13, 17]   # Becomes slow at 19.
149. period, offsets = make_offsets(primes)
150. if __name__ == '__main__':
151.     main()