SHARE
TWEET

prime factor table

a guest May 14th, 2012 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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 ''
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top