On Wed, Dec 30, 2015 at 12:00:02AM +0700, Satya Luzy wrote:
> 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).
[...]
I have had a bit more time available to look at this, and I don't think
your code is correct. I changed the value of n from 94152743499601547 to
18. Factorising 18 should give [2, 3, 3], but your code prints:
1
1
18
2
before ending. I tried it again with n = 459, which should factorise
to [3, 3, 3, 17], but your code prints:
1
1
1
1
1
1
1
1
1
1
18
18
459
9
Then I added an extra line to the faktorisasi_default function, at the
very end:
print 'q =', q, 'p =', p, 'Q =', Q, 'A =', A
and ran it again with n = 459 and got these results:
q = [21, 2, 2, 1, 4, 21, 4, 1, 2, 2, 42,
2, 2, 1, 4, 21, 4, 1, 2, 2, 42,
2, 2, 1, 4, 21, 4, 1, 2, 2, 42,
2, 2, 1, 4, 21, 4, 1, 2, 2, 42,
2, 2, 1, 4, 21, 4, 1, 2, 2, 42]
p = [0, 21, 15, 11, 15, 21,
21, 15, 11, 15, 21,
21, 15, 11, 15, 21,
21, 15, 11, 15, 21,
21, 15, 11, 15, 21,
21, 15, 11, 15, 21,
21, 15, 11, 15, 21,
21, 15, 11, 15, 21,
21, 15, 11, 15, 21,
21, 15, 11, 15, 21]
Q = [1, 18, 13, 26, 9, 2, 9, 26, 13, 18, 1,
18, 13, 26, 9, 2, 9, 26, 13, 18, 1,
18, 13, 26, 9, 2, 9, 26, 13, 18, 1,
18, 13, 26, 9, 2, 9, 26, 13, 18, 1,
18, 13, 26, 9, 2, 9, 26, 13, 18, 1]
A = [0, 1, 21, 43, 107, 150, 248, 309, 107, 416, 21, 458,
438, 416, 352, 309, 211, 150, 352, 43, 438,
1, 21, 43, 107, 150, 248, 309, 107, 416, 21, 458,
438, 416, 352, 309, 211, 150, 352, 43, 438,
1, 21, 43, 107, 150, 248, 309, 107, 416, 21, 458]
(reformatted to make them easier to read). So you can see the problem:
to factorise a 3 digit number, you have recorded over 200 numbers.
And the numbers have repeating patterns, as you can see above.
I don't know if this is expected by the algorithm, or if you have made a
programming error, but this looks very suspicious to me. At the very
least, if you know that these repeating patterns are expected, there is
no need to keep growing the lists and making them bigger and bigger, you
can just build the pattern once.
--
Steve
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
