This week only. Pastebin PRO Accounts Christmas Special! Don't miss out!Want more features on Pastebin? Sign Up, it's FREE!
Guest

prime factor table

By: a guest on May 14th, 2012  |  syntax: Python  |  size: 0.93 KB  |  views: 42  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  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 ''
clone this paste RAW Paste Data