Finding divisors of a number with Python (2019) | Hacker News Reader

Finding divisors of a number with Python (2019)

alexwlchan.net

14 pointsmemorable9 comments

Summary: the divisors of an integer n with prime factorization

   p_1^e_1 * p_2^e_2 * ... * p_k^e_k

are the (e_1+1) * (e_2+1) * ... * (e_k+1) numbers

   p_1^i_1 * p_2^i_2 * ... p_k^i_k with 0 <= i_j <= e_j

In the 80s this was a play around with MSBasic challenge.

"We only need to go up to n/2 because anything larger than that can’t be a divisor of n"

What we learned the hard way in the 80s is mathematically you only need to go up to the sqrt(n) but calculating sqrt(n) in software is so slow compared to n/2, that for the limited numeric range of interpreted basic in the 80s, its faster to check the "excess" numbers between sqrt(n) and n/2. For 16 bit ints figure 15000 or so extra modulus checks was faster than one floating point sqrt().

There's a funny calculus lesson in there, that adding the derivative to the previous sqrt can be kind of useful as you already have an approximation to sqrt(x) from last time around. Just +1 or more to "make sure" your estimated sqrt() increases faster than real sqrt(). Also don't forget if you're only checking odds to increment your sqrt estimate twice.

Programming as a craft never changes, although the problems and associated numbers have varied over the last 40 years or so. Its always been the same people playing the same game.

I think if you’re using a divide-is-integer check you can just assume that if the result is LTE the number supplied, you’ve hit the square root? Currently sitting far from a computer but first impression is it seems right in my head?

That's a good point from memory, remember this is 1980s basic nothing fancy or hardware accelerated, there was a way to do incredibly slow floating point division (software only this was before the 8087 FPU) and there was int division and int modulus so if you wanted to know if the modulus was zero AND the result you'd have to do two slow "divisions" (well, div and mod) but you could do a single mod and a compare to a previously calculated sqrt about twice as fast.

There's actually a sneakier solution I'm surprised no one mentioned, if the challenge is to scan the set of integers in order from 2 to 16 bits, you can cache the sqrt and it max input quite effectively, so the algo is something like have a sqrt "index" and imagine its 7 and now square it and cache that. So... for testing any int up to 49 you check the prime factors up to your cached 7 value. Once you're testing for primes larger than 49, you increase your index, cache its square, and test those numbers until you exceed 81 I guess.

This was a fun 1980s "computer class" challenge because the naive solution of doing a ton of floating point divs and check for remainders while calculating sqrts would take WELL over one class period if not one day if you want a print out of all the prime numbers that fit in 16 bits (which, pitifully, on this interpreted basic, was an int... I don't remember if this was commodore PET (a pre-C64 machine) or something more modern like an Apple II or something newer, technology advanced much faster in the 80s than it does now...). Anyway my claim is I/we eventually calculated all 16 bit primes in well under one class period using considerable optimization.

The only other thing I remember about the challenge is if you print to a line-printer as we did, if you put one prime number on a line you'll get in BIG trouble with the lab supervisor because that'll be about 100 pages printout, but as an exercise in printing tables if you put ten or so primes per line it was a much less wasteful ten pages but if you wrote a string packing algo (another interesting task) that put a single space between each prime while forbidding word wrap, the printout was something like 7 pages. I kept that printout for many years.

In retrospect I'm kind of surprised this ancient basic did unsigned ints instead of signed. That oddity might help someone else remember which 80s interpreted basic this was implemented upon. I was just a kid this couldn't have been something as modern as an Apple II, but maybe? There were a lot of, shall we say, low budget, home computers in the early 80s.

why would you check excess numbers instead of just checking n^2 < end

for (int i=0; i<sqrt(n); i++) == for (int i=0; i*i < n; i++)

^2 is monotonic

Also (n+1)^ = n^2 + 2n +1 i.e. you can have the previous square and just add 2n+1 to it to get the next square (which is 3 additions in total). square += i + i + 1 if square < n; break

I did something like this a while ago while relearning math and python.

  gemTeiler = []
  eingabe = []


  def inputNumber(message):
      while True:
          userInput = input(message)
          return userInput


  def ggT(*args):
      while True:
          zahlen = inputNumber("Bitte Zahlen eingeben: ")
          if zahlen.isdigit():
              teiler = [i for i in range(
                  1, int(zahlen) + 1) if int(zahlen) % i == 0]
              eingabe.append(zahlen)
              gemTeiler.append(teiler)
          elif zahlen.isalpha():
              print("Keine Zahl! Bitte noch einmal versuchen.")
              continue
          elif zahlen == "":
              break


  ggT()
  for i, v in enumerate(eingabe):
      print(f"Die Teiler von {eingabe[i]} sind {gemTeiler[i]}.")
  print(f"Die gemeinsamen Teiler sind: {set.intersection(*map(set, gemTeiler))}")

Yes indeed, basic arithmetic can be used in Python. Is there a greater point to this post I’m missing? I guess we got to see a nice big headshot of the author. Reads sort of like a “I set up an HTTP server with Node and Express” medium blog.

if you know the number is a factorial for example

    9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1

you have are half way of having prime factorization, you can just to compute the prime factor from 1 to 9

and you get

   9! = 3^2 x 2^3 x 7 x 3 x 2 x 5 x 2^2 x 3 x 2 x1

Reply on news.ycombinator.com