Prime factors, divisors, gcd, lcm

A bit of simple arithmetics.
For arbitrary number of integers.
Demonstrate some limits of SB arithmetics. you may enter as many integers as you wish.... in the 'n=[....]' lines are provided some examples, uncomment one of them and symply hit enter...
Also, provided some, from experts provided algorithms, which, due to limitation of integers may give wrong results or, are slow...
Uncomment the lines in the code to see these limitations

And if you need it, use it :)

'SmallBASIC,0.12.8 Android Sat, 22 Oct 2016, [jsalai49]
' Prime factors, divisors, gcd, lcm for integers
color 15,0
while 1
  ?:?"Enter integers > 1 for Factor, GCD and LCM"
  i=1:dim n
'  n=[12,23,34,45,56,67,78,89,91]
'  n=[123,234,345,456,567,678,789,891]
'  n=[1234,2345,3456,4567,5678,6789,7891] 'gcde - no ok
'  n=[12345,23456,34567,45678,56789,67891]
'  n=[123456,234567,345678,456789,567891] ' dv - slow
'  n=[1234567,2345678,3456789,4567891]
  while 1
    repeat
      ?"No-";i,:input,k:j=k in n
    until j=0
    if k<2:cls:if !len(n):stop:fi:exit loop:fi
    n << k:i++
  wend
  ?"Number";tab(12);"[Prime factors]"
  ?"[All divisors of given number]"
  u=pfact(n(0)):v=u:g=n(0):l=g
  for x in n
    f=pfact(x):?x;tab(12);f:?div(f)
'    ?dv(x,f(0))
    if len(v):v=gcd(v,f):fi:u=lcm(u,f)
    if g>1:g=gcde(g,x):fi:l=l*(x/gcde(l,x))
  next
  p=1:for x in v do p*=x:?:?"gcd:",p,v
  o=1:for x in u do o*=x:?"lcm:",o:?u
'  ?:?"gcde:",g,pfact(g):?"lcme:",l:?pfact(l)

  input,xxxx:cls
wend

func div(@f)
  'replacement for the function below, based on all
  'combinations of primes, and their unique products
  local i,k,l,m,t,u,y
  m=len(f):y=[1]:l=m:dim t:for i=0 to m-1 do t << i
  for k=1 to m:dim u(k-1):comb(m,k):next:sort y:div=y
  sub comb(n,c)
    local a,b
    if c=0
      a=1:for b in u:a*=f(b):next
      if !(a in y):y << a:fi:exit sub:fi
    if n=0 then exit sub
    u(k-c)=t(l-n):comb n-1,c-1:comb n-1,c
  end
end

func dv(n,o)
  'find all divisors of an integer; brute-force, cited
  'in Rosetta code, although correct, hopelessly slow,
  'specially for large integers
  local i,a
  if n<1:exit func:fi
  for i=1 to n/o:if !(n%i):a << i:fi:next:a << n:dv=a
end

func pfact(x)
  local f,q,s,d
  s=sqr(x):f=2:dim d
  while x>1
    q=x/f
    if q=int(q)
    d << f:x=q
    else
      f=if(f=2,3,f+2):if f>s:f=x:fi
    fi
  wend
  pfact=d
end

func lcm(a,b)
  local i,j,d
  for i in a:j=i in b:if j:delete b,j-1:fi:next
  d=a:for i in b:d << i:next:sort d:lcm=d
end

func gcd(a,b)
  local i,j,d
  dim d:for i in a:j=i in b:if j:delete b,j-1:d << i:fi
  next:gcd=d
end

func gcde(a,b)
  'euclidian algorithm is of course much better when
  'arbitrary precision arithmetics present, but now for
  'a few large numbers, or several small numbers gives
  'wrong results - "b=a%b" replaced by "b=a-int(a/b)*b"
  'gives some slight improvements
  local t
  if a<b:swap a,b:fi
  while b
    t=b:b=a-int(a/b)*b:a=t
  wend
  gcde=a
end

Enter a few integers and hit [enter]
If lazy, uncomment the n=[....] line and hit enter.

Hope, somebody may find it interesting...

Cheers!

'SmallBASIC,0.12.8 Android Sat, 22 Oct 2016, [jsalai49]
color 15,0
while 1
  ?:?"Enter integers > 1 for LCM"
  i=1:dim n,o
'  n=[12,234,34,456,56,678,78,890,9,232]
  while 1
    repeat:?"No-";i,:input,k:j=k in n:until j=0
    if k<2:cls:if !len(n):stop:fi:exit loop:fi
    n << k:i++
  wend
  l=pfact(n(0)):a=len(n)-1
  for x in n:f=pfact(x):l=lcm(l,f)
    o << string(len(x)+1,"#"):next
  for j=0 to len(l)-1:c=l(j)
    for i=0 to a:x=n(i):?usg(o(i));x;
      if x%c=0:x/=c:n(i)=x:fi:next
    ?" | ";c:next
  for i=0 to a:?usg(o(i));n(i);:next:?" | "
  o=1:for x in l do o*=x:?"lcm:";o
  sprint z;l:z=translate(disclose(z,"[]"),",","*"):?z
  input,xxxx:cls
wend

func pfact(x)
  local f,q,s,d
  s=sqr(x):f=2:dim d
  while x>1
    q=x/f
    if q=int(q)
      d << f:x=q
    else
      f=if(f=2,3,f+2):if f>s:f=x:fi
    fi
  wend
  pfact=d
end

func lcm(a,b)
  local i,j
  for i in a:j=i in b:if j:delete b,j-1:fi:next
  for i in b:a << i:next:sort a:lcm=a
end

Looking for practical applications of LCM, I ran into the hot dog solution.

What is the least amount of bun packages sold 8 buns to package and least amount of hot dog packages sold 10 per pack do you have to buy to get the same amount of hot dogs and buns?

Right, 0! ;-))

More homework help (with bonus solution to hot dog with napkins problem):

EDIT 2016-11-18: Opps! the strProperFraction function needed fixing up!


' Add fractions with lcm.bas SmallBASIC 0.12.8 [B+=MGA] 2016-11-17
' 2016-11-18 fix proper fractions for negatives and 0's

'debug strProperFraction to fix sub
if 0 then '<<<< cool way to comment out block of code
repeat
?:input "(0 quits) Enter improper fraction n/d to check function ";ff
n1 = leftof(ff ,"/")
d1 = rightof(ff, "/")
? " and the proper fraction is ";strProperFraction(n1, d1)
until
n1 = 0 or d1 = 0
end
if

'if 0 then 'while debugging strProperFraction don't need this
'hot dogs and napkins (300 napkins per pack)
? "Hot dogs are 8 per pack"
? "Buns are 6 per pack"
? "Napkins are 300 per pack"
? "I must buy ";lcm(lcm(8, 6), 300);" hotdogs, buns, napkins for no leftovers."
?
repeat
?:? "Add fractions:
input "(0's quit) Enter numerator/denominator of first fraction ";ff
n1 = leftof(ff ,"/")
d1 = rightof(ff, "/")
if n1 <> 0 and d1 <> 0 then
input "(0's quit) Enter numerator/denominator of 2nd fraction ";ff
n2 = leftof(ff ,"/")
d2 = rightof(ff, "/")
if n2 <> 0 and d2 <> 0 then
? "and the sum is ";strAddFractions(n1, d1, n2, d2)
fi
fi
until n1 = 0 or n2 = 0 or d1 = 0 or d2 = 0
'end if
?:? "Good-bye"
pause

func
factors(n) 'there is a limit on how great n can get
'modified to handle fractions and other wierd inputs
local rtn, fd, test
dim rtn()
n = int(n)
if n < 0 then rtn << -1 : n = n * -1
if n > 1 then
repeat
fd = 0 : test = 2
while test <= n ^.5
if n % test = 0 then fd = test : exit loop
if test = 2 then test = 3 else test = test + 2
wend
if fd then n /= fd : rtn << fd else rtn << n
until fd = 0
elseif n = 1
rtn << 1
elseif n = 0
rtn << 0
end if
factors = rtn
end

func
lcm(n, m)
local rtn, nf, mf, i, j
rtn = 1
nf = factors(n)
mf = factors(m)
'this next block is genius, thanks jsalai!
for i in nf
rtn *= i 'well, I added this since we are here
j = i in mf
if j then delete mf, j-1 'why j-1? j-1 is index of j?
'it works!!!
next
'but why not finish lcm with single number?
for i in mf
rtn *= i
next
lcm = rtn
end

func
strAddFractions(n1, d1, n2, d2)
local lm, n
lm = lcm(d1, d2)
n = n1 * int(lm/d1) + n2 * int(lm/d2)
strAddFractions = strProperFraction(n, lm)
end

func
strProperFraction(numerator, denominator)
local n, d, strRtn, nF, dF, i, j, mult, integer
n = int(numerator)
d = int(denominator)
mult = 1
strRtn = ""
if n < 0 and d < 0 then n = -n : d = -d
if n < 0 then strRtn = "-" : n = -n
if d < 0 then strRtn = "-" : d = -d
if d = 0 then
strRtn = "undefined"
elseif n = 0 and d <> 0
strRtn = "0"
elseif n = d
strRtn = strRtn + "1"
else
if n > d then
integer = int(n/d)
n = n - integer * d
strRtn = strRtn + str(integer)
end if
nF = factors(n)
dF = factors(d)
for i in dF 'sort of copy method in lcm
j = i in nF
if j then delete nF, j-1 : mult *= i
next
n /= mult
d /= mult
if n <> 0 then
if integer then strRtn = strRtn + " and "
strRtn = strRtn + str(n) + "/" + str(d)
end if
end if
strProperFraction = strRtn
end



Dang, I guess we are only adding improper fractions and making answer a proper fraction.

As you probably noticed, I'm a very awfully bad/poor programmer.
Don't care about structures, local variables (when not necessary), readability, etc...
Being an assembler (Z80, 8085, DPS/6, 86-586), COBOL, Pascal, VBA, (a litle bit of) C/C++ programmer, I'm trying to write compact, efficient code (with more/less success).
Don't compete, don't teach, rarely comment, but enter any of my programs written 30-35 years ago...

Now, for prime factorization
I don't extend it to negative, 0 or 1, nor floating point numbers. My tribute to good old Eratosthenes


'this next block is genius, thanks jsalai!

you are welcome. IMHO, nothing genial, simple use of SB array 'qualities'


'but why not finish lcm with single number?

- no need to compose-factorize each time for more numbers
- in case of bigger nums, afterwards you cannot factorize it back correctly
- one may see how the 'lcm' is composed
- finally, I do it, when needed

And now, in my very bad habit:

PS. Added a few details for unexperienced children :)

color 15,0:u=" = ":v="/"
while 1
  cls:?:? "Add fractions:"
  i=1:dim n,d,f:z=""
  while 1
    ?i;". [n/d]: ";:input,j
    x=val(leftof(j,v)):y=val(rightof(j,v))
    if !y:if len(n)=0:cls:stop:fi:exit loop:fi
    if x*y:n << x:d << y:f << j:i++:fi
  wend
  l=pfact(d(0)):a=len(n)-1:locate 1+i,0:?spc(40)
  for x in d:q=pfact(x):l=lcm(l,q):next
  o=1:for x in l do o*=x
  p=0:y="":for i=0 to len(n)-1:x=n(i)*o/d(i):p+=x
  y+=if(x<0 or !len(y),x,"+"+x)+"/"+o:next
  for i in f:z+=if(left(i)="-" or !len(z),i,"+"+i):next
  ?z;u:?u;y;u:?u;p;v;o;:g=gcd(p,o)
  if g>1:p/=g:o/=g:?u;p;v;o;:fi
  if p>=o:?u;p\o;:if p%o:?" [";p%o;v;o;"]";:fi:fi:?:?
  ?"press [enter]",:input,xxx
wend
func pfact(x)
  local f,q,s,d
  s=sqr(x):f=2:dim d
  while x>1
    q=x/f
    if q=int(q)
      d << f:x=q
    else
      f=if(f=2,3,f+2):if f>s:f=x:fi
    fi
  wend
  pfact=d
end
func lcm(a,b)
  local i,j
  for i in a:j=i in b:if j:delete b,j-1:fi:next
  for i in b:a << i:next:sort a:lcm=a
end
func gcd(p,o)
  local i,j,q,d,a,b
  a=pfact(p):b=pfact(o)
  dim d:for i in a:j=i in b:if j:delete b,j-1:d << i:fi
  next:q=1:for i in d:q*=i:next:gcd=q
end