xenny-and

Xenny has 2 positive integers A and B. He wants to find the prime factorization of the integer A^B.

Input format:

Each line contains 2 space-separated integers A and B.

Output format:

Consider A^B to have N prime factors.
Print N lines.
For every prime factor, print the base and the exponent separated by a single space.
The prime factors must be sorted by base.

Constraints:

1 ≤ A ≤ 10^12

1 ≤ B ≤ 1000

SAMPLE INPUT
10 1

SAMPLE OUTPUT
2 1
5 1

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY
Tags: Number theory


Solutions:
import math
primelist=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]
skiplist=[1,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,179,191,193,197,199]

def isprime(p):
#    print p
	i=0
	temp=math.sqrt(p)
#    print temp
	while(primelist[i]<temp):
#        print primelist[i]
		if(p%primelist[i]==0):
			break
		else:
			i=i+1
	if(primelist[i]>temp):
#        primelist.append(p)
		return 1
	else:
		return 0
a,b=list(map(int,input().split()))
sqrt_a=math.sqrt(a)
list_limit=int(sqrt_a/200)
if a==1:
	print(a,a)
for i in range(1,list_limit):
	for j in range(0,43):
		temp=210*i+skiplist[j]
		if(isprime(temp)):
			primelist.append(temp)
#            print temp
#print primelist[-1]
for z in primelist:
	count=0
	while(a%z==0):
 #       print "The a is:",a,"The z is:",z
		a=a/z
		count+=1
#        print "now a is:",a
	if(count>0):
		print(z,count*b)
	if a<=1:
 #       print "before breaking",a
		break
else:
	print(a,b)