1. #return least prime factor
  2. def sieveLpf(n):
  3.     #list odd numbers less than or equal to the square root of n
  4.     odd = []
  5.     a = 3
  6.     while a*a <= n:
  7.         odd.append(a)
  8.         a = a + 2
  9.        
  10.     #list prime numbers
  11.     for p in odd:
  12.         q = 2*p
  13.         while p <= odd[-1]:
  14.             p = p + q
  15.             if p in odd:
  16.                 odd.remove(p)
  17.                
  18.     #get least prime factor
  19.     for i in odd:
  20.         if n % i == 0:
  21.             return i
  22.    
  23.     return '--'
  24.    
  25. def buildTable(n):
  26.     #odd should contain odd numbers except those divisible by 5
  27.     odd = []
  28.     a = 1
  29.     while a <= n:
  30.         if a % 5 != 0:
  31.             odd.append(a)
  32.         a = a + 2
  33.        
  34.     #output formatting 
  35.     for i in range(-1, 10):
  36.         if i == -1:
  37.             print '{0:5s}'.format(''),
  38.         else:
  39.             print '{0:5d}'.format(i),
  40.        
  41.     print ''
  42.    
  43.     for i in odd:
  44.         print '{0:5d}'.format(i),
  45.         for j in range(0, 10):
  46.             x = int(str(j) + str(i))
  47.             x = sieveLpf(x)
  48.             if isinstance(x, int):
  49.                 print '{0:5d}'.format(x),
  50.             else:
  51.                 print (x).rjust(5),
  52.         print ''