#return least prime factor
def sieveLpf(n):
#list odd numbers less than or equal to the square root of n
odd = []
a = 3
while a*a <= n:
odd.append(a)
a = a + 2
#list prime numbers
for p in odd:
q = 2*p
while p <= odd[-1]:
p = p + q
if p in odd:
odd.remove(p)
#get least prime factor
for i in odd:
if n % i == 0:
return i
return '--'
def buildTable(n):
#odd should contain odd numbers except those divisible by 5
odd = []
a = 1
while a <= n:
if a % 5 != 0:
odd.append(a)
a = a + 2
#output formatting
for i in range(-1, 10):
if i == -1:
print '{0:5s}'.format(''),
else:
print '{0:5d}'.format(i),
print ''
for i in odd:
print '{0:5d}'.format(i),
for j in range(0, 10):
x = int(str(j) + str(i))
x = sieveLpf(x)
if isinstance(x, int):
print '{0:5d}'.format(x),
else:
print (x).rjust(5),
print ''