Rating: 4.3

In this we had to factorize
n = 2462649746477364143454082050368305440553491900304388646893610847386194301369924385009730987303651345060031438478297733694036327257723431468649220444397635127530301992505638291521092898714917678389314956983918603221732358628680256253537449204312287724750669208856634711056863315465220853759428826555838536733

Admins released the hint that the primes are close by, so I tried fermat factorization.
Since standard implementations are pretty slow, I found that yafu has a pretty optimized version with sieve improvement. But yafu was returning 1 as the primes, so I compiled it again and debugged to see the problem.
Yafu was crashing after found: in trialdiv.c


mpz_add_ui(a, a, count);

if ((mpz_size(b2) > 0) && mpz_perfect_square_p(b2))
printf("found square at count = %d: a = %s, b2 = %s",count,

So instead of finding the problem I basically copied the value of count using gdb and used the below py script to get the factors:

count = 26365624027328
a = gmpy.sqrt(self.n) + count
max = a + self.limit
b2 = a*a - self.n
b = gmpy.sqrt(b2)
p = a+b
q = a-b
print p, q
Finally the primes

grocid – Sept. 15, 2017, 11:15 p.m.

Whoa, I was quite surprised to see a factoring solution of the challenge. Nice job :-) Anyways, intended solution is here https://grocid.net/2017/09/16/finding-close-prime-factorizations/