Factorise

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

Last modified	2016-10-17
Lines	162

Parent directory Download CGIread sitemap Main page

Quick links: factorise main make_offsets

```
#!/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()
```