0

My number has 617 digits. What is the fastest way to find the prime factors of this large number?

My number in question is 19087688894909892783503691960213776632781962588843842839953893606139157282825376128877238229887486797933180624979637419997128020864299273315243907454874577263432419226852240380380880131843664800828228959920799327101817796594944161768692639537839544009100224905464911818390882192901883104039350105285757995782376058970382205463192526628231366854662473466838863987148898819243940809068605863725041711337107340279029811816555169181781669826715177100102639379572663639848699896757952171115689208069972249342540932428107175784150214806633479073061672324629925288020557720111253896992657435200329511186117042808357973613389

Please help. Thank you!

Maqruis1
  • 157
  • 1
  • 1
  • 13
  • @KlausD. do u have a solution for dealing with such a large input? the below solution doesn't work cos the size of the integer in question is too large to convert to a float – gireesh4manu Jan 18 '19 at 13:29
  • 1
    Nearly all of our encryption on the internet depends on the large complexity involved in finding the prime factors of large numbers. If I would know an efficient solution I would have to make a decision: a) keep it for me, and become very rich b) publish it and destroy the internet as be know it. Hard choice! ;-) – Klaus D. Jan 18 '19 at 14:51
  • Lol! True that! – gireesh4manu Jan 19 '19 at 06:37

1 Answers1

0

I've made some changes to the github implementation for getting the correct output as below.

1.In python 3, range() doesn't automatically return a list, so i made it list(range(n+1))

2.I made it int(n/i-i)

import math

# return a dict or a list of primes up to N
# create full prime sieve for N=10^6 in 1 sec
def prime_sieve(n, output={}):
    nroot = int(math.sqrt(n))
    sieve = list(range(n+1))
    sieve[1] = 0

    for i in range(2, nroot+1):
        if sieve[i] != 0:
            m = int(n/i - i)
            sieve[i*i: n+1:i] = [0] * (m+1)

    if type(output) == dict:
        pmap = {}
        for x in sieve:
            if x != 0:
                pmap[x] = True
        return pmap
    elif type(output) == list:
        return [x for x in sieve if x != 0]
    else:
        return None

Then, in the below function i made default value of primelist=None

def get_prime_factors(n, primelist=None):
    if primelist is None:
        primelist = prime_sieve(n,output=[])

    fs = []
    for p in primelist:
        count = 0
        while n % p == 0:
            n /= p
            count += 1
        if count > 0:
            fs.append((p, count))

    return fs

Now, if you try: 

print(get_prime_factors(140))

you get the correct output: 

[(2, 2), (5, 1), (7, 1)]
gireesh4manu
  • 109
  • 2
  • 12