Hello, I am currently working on a program to find the prime factor of n, in which n is a big integer. Using the Continued Fraction factorization method (I will provide the source code below, please don't mind the variables). It works perfectly when factorizing below 10 digits numbers. In my code below you will see on how I tried to factorize 94152743499601547, but get this message instead : --------------------------------------------------------------------------------------------------------------------- *Traceback (most recent call last):* * File "C:/Users/Satya/PycharmProjects/untitled2/fact.py", line 94, in <module>* * faktorisasi(n)* * File "C:/Users/Satya/PycharmProjects/untitled2/fact.py", line 92, in faktorisasi* * faktorisasi_default(n,j,boundary)* * File "C:/Users/Satya/PycharmProjects/untitled2/fact.py", line 55, in faktorisasi_default* * Q.append(((n*kelipatan)-(p[i]**2))/Q[i-1])* *MemoryError*
*Process finished with exit code 1* -------------------------------------------------------------------------------------------------------------------- It has undergone the boundary value of 51200 and j value of 12. It has been running for more than 5 hours before it suddenly stop. Please let me know how to fix the memory error, Thanks before. Sincerely. -------------------------------------------------------------------------------------------------------------------- [CODE] import fractions import math n = 94152743499601547 #untuk difaktorkan flag = True faktor_1 = 1 #deklarasi asal faktor_2 = 1 # CFRAC def cfract(n,boundary): coeff = 1 floor_part = floor_ = math.floor(math.sqrt(n)) denom = n - floor_part ** 2 result = [] result.append(int(floor_)) if float(denom)!=0: for i in range(boundary-1): try: floor_ = math.floor((math.sqrt(n) + floor_part) / float(denom)) except ZeroDivisionError: # perfect square return result if denom != 1: result.append(int(floor_)) floor_part = denom * floor_ - floor_part coeff = denom denom = n - floor_part ** 2 common_div = fractions.gcd(coeff, denom) coeff /= common_div denom /= common_div if denom == 1: result.append(int(floor_part + result[0])) return result def faktorisasi_default(n,kelipatan,boundary): global faktor_1,faktor_2,flag q = cfract(n*kelipatan,boundary) p = [] Q = [] A = [] p.append(0) p.append(q[0]) Q.append(1) A.append(0) A.append(1) A.append(q[0]) Q.append(((n*kelipatan)-(p[1]**2))/Q[0]) # i = 2 for i in range(2,len(q)): p.append((q[i-1]*Q[i-1])-p[i-1]) Q.append(((n*kelipatan)-(p[i]**2))/Q[i-1]) A.append((q[i-1]*A[i]+A[i-1])%(n*kelipatan)) #tabel sudah selesai temp = 0 # nilai Q yg ganda temp2 = 0 tempA1 = 0 # nilai A dari Q1 tempA2 = 0 # nilai A dari Q2 for i in range(0,len(Q)): for j in range(i+1,len(Q)): if flag and Q[i]==Q[j]: print Q[i] print Q[j] temp = Q[i] tempA1 = A[i+1] tempA2 = A[j+1] temp2 = tempA1*tempA2 % n # nilai base if temp2 > Q[i]: faktor_1 = int(fractions.gcd(temp2+temp,n)) faktor_2 = int(fractions.gcd(temp2-temp,n)) if faktor_1 != 1 and faktor_2 != 1: flag = False def faktorisasi(n): global flag j=1 #kelipatan boundary=50 #iterasi CFRAC faktorisasi_default(n,j,boundary) while (flag): j+=1 boundary*=2 print "Nilai boundary : %d" %boundary print "Nilai j : %d" %j faktorisasi_default(n,j,boundary) faktorisasi(n) print faktor_1 print faktor_2 _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor