Summary: the divisors of an integer n with prime factorization<p><pre><code> p_1^e_1 * p_2^e_2 * ... * p_k^e_k
</code></pre>
are the (e_1+1) * (e_2+1) * ... * (e_k+1) numbers<p><pre><code> p_1^i_1 * p_2^i_2 * ... p_k^i_k with 0 <= i_j <= e_j</code></pre>
In the 80s this was a play around with MSBasic challenge.<p>"We only need to go up to n/2 because anything larger than that can’t be a divisor of n"<p>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().<p>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.<p>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 did something like this a while ago while relearning math and python.<p><pre><code> 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))}")</code></pre>
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<p><pre><code> 9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
</code></pre>
you have are half way of having prime factorization, you can just to compute the prime factor from 1 to 9<p>and you get<p><pre><code> 9! = 3^2 x 2^3 x 7 x 3 x 2 x 5 x 2^2 x 3 x 2 x1</code></pre>