Hi,
am trying this problem but getting wrong answer I think my approach is correct.
can someone help me
problem link spoj.com/problems/NAJMBN/
Thanks.
[bbone=python,746]import sys,math
def is_prime(n):
"""
False if n is provably composite, else
True if n is probably prime; assumes n
is an integer greater than 1; uses
Miller-Rabin test on prime bases < 100
"""
ps = [2,3,5,7,11,13,17]
def is_spsp(n, a):
d, s = n-1, 0
while d%2 == 0:
d /= 2; s += 1
if pow(a,d,n) == 1:
return True
for r in xrange(s):
if pow(a, d*pow(2,r), n) == n-1:
return True
return False
if n in ps: return True
for p in ps:
if not is_spsp(n,p):
return False
return True
def factors(n):
"""
list of prime factors of n in ascending
order; assumes n is an integer, may be
positive, zero or negative; uses Pollard's
rho algorithm with Floyd's cycle finder
"""
def gcd(a,b):
while b: a, b = b, a%b
return abs(a)
def facts(n,c,fs):
f = lambda(x): (x*x+c) % n
if is_prime(n): return fs+[n]
t, h, d = 2, 2, 1
while d == 1:
t = f(t); h = f(f(h))
d = gcd(t-h, n)
if d == n:
return facts(n, c+1, fs)
if is_prime(d):
return facts(n//d, c+1, fs+[d])
return facts(n, c+1, fs)
if -1 <= n <= 1: return [n]
if n < -1: return [-1] + factors(-n)
fs = []
while n%2 == 0:
n = n//2; fs = fs+[2]
if n == 1: return fs
return sorted(facts(n,1,fs))
def main():
y=1;f=0
num=int(sys.stdin.readline().strip())
#print num
if num < 0:
f=1
num*=-1
#print "I am here"
if num==1 or num==0:
print "-1"
elif(is_prime(num)):
sys.stdout.write("-1\n")
else:
bb=factors(num)
for val in bb:
x=val
y*=val
if f==1:
print min(x*-1,y//x),max(x*-1,y//x)
else:
print min(x,y//x),max(x,y//x)main()
[/bbone]