Factorization: What went wrong with d?

Question

Consider:

Input: 20
       17
       999997

Output: 2^2 * 5
        17
        757 * 1321

My code:

a = int(input())

# Find the factors first
for i in range(2, a+1):

    s = 0
    b = a
    d = 0

    # See if it is a prime number
    if a%i == 0:
        for x in range(1, i+1):
            if a%x == 0:
                d = d + x

        if (d-1)/i == 1:
            d = 0
            print(i)
        else:
            s = 0
            b = a
            d = 0

            continue

            d = 0

        # I will see how many prime numbers
        while(b>0):

            if (b/i)%1 == 0:
                s = s + 1
                b = b/i
            else:
                b = 0
                if b == 1:
                   b = 0

        print(s)

I will find the factors first, and then see if it is a prime number. If so, I will see how many prime numbers it is

if i input 12, it outputs 2 2

Enter link description here

As a side note: please refrain from inserting blank lines after each line of code, it makes it much harder and unpleasant to read. — Thierry Lathuille, Nov 21 '20 at 13:12
If your code doesn't do what you expect it to, please provide the output vs expected output. If you get an error, please provide the complete error traceback. — Thierry Lathuille, Nov 21 '20 at 13:14
This script is running successfully, I think in `a=int(input("Enter no. here"))` you have not included any message so on executing you might be seeing as stucked. — Ranjeet SIngh, Nov 21 '20 at 13:19
@RanjeetSingh It isn't running successfully, it does find the first factor and associated exponent, but not the others — OctaveL, Nov 21 '20 at 13:21
i dont know what is continue mean,i use it first time,when one loop go through,d become very strange — 蔡銘恩, Nov 21 '20 at 13:23
@蔡銘恩 The keyword `continue` ends the current loop iteration and goes to the next one. In simpler terms, it won't execute the code that comes after the `continue` and will go back to the top of the loop instead — OctaveL, Nov 21 '20 at 13:26
@蔡銘恩 what is your expected output on 20 and what are you actually getting, can you share that as well? — Ranjeet SIngh, Nov 21 '20 at 13:27
@RanjeetSingh His expected output is `2 2 5`, and the script returns `2 2` instead (with newlines instead of spaces) — OctaveL, Nov 21 '20 at 13:29

score 3 · Answer 1 · edited Dec 29 '22 at 01:23

I believe you need the output of the following.

import math

a = int(input())
while (a % 2 == 0):
    print(2)
    a = int(a/2)
while (a % 3 == 0):
    print(3)
    a = int(a/3)
for i in range(5, math.ceil(math.sqrt(a)), 6):
    while (a % i == 0):
        print(i)
        a = int(a / i)
    while (a % (i + 2) == 0):
        print(i + 2)
        a = int(a / (i + 2))
if (a > 3):
    print(a)

This will give you the prime factors for a given number. As I can understand, it is what you are looking for.

score 2 · Accepted Answer · answered Nov 21 '20 at 13:38

2

a = int(input("Enter a number:"))

for i in range(2, a + 1):
    if a % i != 0:
        continue

    # SETTING THE DEFAULT VALUES AT THE BEGINNING OF EVERY ITERATION OF THE LOOP
    s = 0
    b = a
    d = 0

    for x in range(1, i + 1):
        if b % x == 0:
            d = d + x

    if (d - 1) / i == 1:
        d = 0
        print(i)
    else:
        # s = 0 # NO LONGER NEEDED, AS WE RESET THEM AT THE BEGINNING OF THE LOOP
        # b = a
        # d = 0
        continue

    while b > 0:
        if (b / i) % 1 == 0:
            s = s + 1
            b = b / i
        else:
            b = 0
            if b == 1:
                b = 0

    print(s)
    a /= i**s # THIS LINE IS IMPORTANT

You were close. You forgot to set the default values at the beginning of every iteration of the loop, so they sometimes didn't have the right values ; and you should set a to a different value by dividing it by the factor you found (i**s, so i to the power of s).

As has been mentioned, your code also follows an odd coding style. I suggest you stop putting newlines between each statement, and start separating operators with spaces (example: range(3+5) is bad, range(3 + 5) is more readable)

answered Nov 21 '20 at 13:38

OctaveL

1,017
8
18

can you please tell me what a /=i**s meaning – 蔡銘恩 Nov 21 '20 at 13:54
i have another question – 蔡銘恩 Nov 21 '20 at 14:26
my output is 2^2 * 5 – 蔡銘恩 Nov 21 '20 at 14:27
but i will get 1 more * – 蔡銘恩 Nov 21 '20 at 14:27
become 2^2* 5 * – 蔡銘恩 Nov 21 '20 at 14:30
@蔡銘恩 `a /= i**s` is the equivalent to `a = a / i**s` ; and `i**s` is `i` to the power of `s`. I divided `a` by the value of the factor you found, so that we may find the next factors that make `a`'s prime factorization after having removed the one we already found. I find it hard to explain, but for example, here we found `2**2` for 20 ; so we divide 20 by 4, and we get 5. It's now 5 whose prime factorization we want and by finding it we'll find 20's factorization. Apologies for how complex this sounds. There are much better implementations out there. Also, I don't get that new question. – OctaveL Nov 21 '20 at 15:51

score 1 · Answer 3 · edited Dec 29 '22 at 01:33

You are using too many loops here and that's why you are getting too much confused. Here is the code which serve the same purpose (if I understand your problem correctly)

a = int(input("Enter a number: "))
i = 2
factors = []
while i <= a:
    if (a%i) == 0:
        factors.append(i)
        a = a/i
    else:
        i = i + 1
print(factors)

here I am returning a list, if you want you can change the type accordingly.

Here are the inputs/outputs:

Enter a number: 17
[17]

Enter a number: 100
[2, 2, 5, 5]

Enter a number: 12
[2, 2, 3]

Factorization: What went wrong with d?

3 Answers3