3
\$\begingroup\$

I have created a simple code which finds the factors of any given integer. It then compares the value of the input to the range of numbers. Because a prime number can factorize into 1 and itself. Then I search length of the factor list. If the list contains 2 or less elements it is added to the all_primes list. I have flattened the list and also produced a list with the composite numbers missing for pattern recognition.

Is this a good method to find the Prime numbers and factors of a value and is there any bugs I can encounter?

all_primes = []

def user_in(num):
    while True:
        if num <= 2:
          break
        num -= 1
        numbers = [i for i in range(1, num + 1)]
        factors = [i for i in numbers if num % i == 0]
        primes = [i for i in factors if len(factors) <= 2 and i != 1]
        all_primes.append(primes)
        print('Number: {}\nFactors: {}\nFactor count: {}\nSum of factor: {}\nSum of numbers: {}\nSum of Primes: {}\n\n'.format(num, factors, len(factors), sum(factors), sum(numbers), sum(primes), primes))

x = int(input('Enter number: '))
user_in(x)
all_primes.reverse()
flat_list = [i for k in all_primes for i in k]
print('Flat list of Primes: {}\n\nSum of all primes: {}\n\nAll Primes: {}'.format(flat_list, sum(flat_list) + x, all_primes))

This example is part of the output:

Number: 5
Factors: [1, 5]
Factor count: 2
Sum of factor: 6
Sum of numbers: 15
Sum of Primes: 5


Number: 4
Factors: [1, 2, 4]
Factor count: 3
Sum of factor: 7
Sum of numbers: 10
Sum of Primes: 0


Number: 3
Factors: [1, 3]
Factor count: 2
Sum of factor: 4
Sum of numbers: 6
Sum of Primes: 3


Number: 2
Factors: [1, 2]
Factor count: 2
Sum of factor: 3
Sum of numbers: 3
Sum of Primes: 2


Flat list of Primes: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Sum of all primes: 378

All Primes: [[2], [3], [], [5], [], [7], [], [], [], [11], [], [13], [], [], [], [17], [], [19], [], [], [], [23], [], [], [], [], [], [29],[], [31], [], [], [], [], [], [37], [], [], [], [41], [], [43], [], [], [], [47], [], []]
\$\endgroup\$
2
  • \$\begingroup\$ Why are you starting from num -= 1 , skipping the initial number? When user enters 5 - the processing starts with 4 \$\endgroup\$ Dec 22, 2019 at 6:45
  • \$\begingroup\$ Seemed the simplest way to iterate through all the numbers of the up to the input. I compensate by adding the + input into the list and the sum. This then shows all the primes up to the number chosen. Do you have any suggestions to improve it? \$\endgroup\$
    – Barb
    Dec 22, 2019 at 11:01

1 Answer 1

3
\$\begingroup\$

I have to state right at the start, I don't know what your code does. That's ok. I'm going to stream-of-conciousness review the code, so you'll get all my thoughts and improvements as it goes on. Maybe that's a good thing.

Global Variables

Global variables are frowned upon. They make code harder to test and harder to reason about. The function user_in modifies all_primes. What value(s) can all_primes have before the function runs? If the function is run more than once, does more stuff get added to all_primes? Does stuff get replaced? Is the result corrupted?

In this case, the global variable is easy to get rid of. Instead of modifying a global all_primes variable, how about returning it?

def user_in(num):
    all_primes = []
    while True:
        ...
        all_primes.append(primes)
        ...
    return all_primes

...
all_primes = user_in(x)
...

Now you can run user_in() several times with different input values, and actually test that the right value is returned in your test cases.

Method Naming

What does user_in() do? It sounds like it might ask the user for some input, but it isn't clear what that input might be.

But reading the user_in() method, it doesn't ask for any input at all! Rather, the mainline code ask the user to enter a number, and this number is given as an input to the user_in() method. A better name would be process_and_output(), but that is still a horrible name; it doesn't say what kind of processing is being done, nor what kind of output is produced. Moreover, the method is producing output and it is (now) returning a value. Functions should do one logical thing, and be named after what it does.

Ranges, Lists, and Iterables

The statement numbers = [i for i in range(1, num + 1)] constructs a range object with the numbers from 1 to num inclusive, takes successive numbers in that range, and extracts them into a list. The remainder of the code iterates over the values stored in numbers.

Why?

First of all, numbers = list(range(1, num + 1)) would be a shorter way of expressing the construction of numbers.

Second, why realize a physical list of numbers when you are just going to iterator over it, and a range() object itself is iterable? Just use the range object.

numbers = range(1, num + 1)

Factorization

factors = [i for i in numbers if num % i == 0]

This is fine, but it is inefficient. Factors come in pairs. If num % i == 0, then i is a factor and num // i is also a factor. If you recorded both, then instead of looping over all numbers, you could loop up to math.isqrt(num) + 1. If num is one million, this would save you nine hundred and ninety nine thousand trial divisions! Note, you would have to watch for the special cases of num being a perfect square: you would want to generate that factor exactly once.

Move Constant Expressions Out of Loops

What does this statement do?

    primes = [i for i in factors if len(factors) <= 2 and i != 1]

First, look at the len(factors) <= 2 condition. Can it change during the loop, or will it always be either True or False? The list of factors doesn't change, so clearly the length is constant. So we could write this as a two statements:

    if len(factors) <= 2:
        primes = [i for i in factors if True and i != 1]
    else:
        primes = [i for i in factors if False and i != 1]

Simplifying if True and anything to if anything, as well as if False and anything to "never", we get:

    if len(factors) <= 2:
        primes = [i for i in factors if i != 1]
    else:
        primes = []

Moreover, if there are 2 or less factors, those factors are 1 and num. Since you are filtering out the i == 1 factor, you will always be left with the second factor, if it exists, which will always be num:

    if len(factors) == 2:
        primes = [num]
    else:
        primes = []

Then, you are adding this list to all_primes, and later flattening the list, to remove the empty lists which you added.

How about, just adding the prime you found to all_primes, and not generating a list of lists?

    if len(factors) == 2:
        all_primes.append(num)

Printing

That is a rather long print statement. Any reason for making it that long? Maybe split it up into the equivalent 7 print statements? We've gotten rid of primes, which contained 0 or 1 value, so computing the "sum of primes" needed to be adjusted. It begs the question as to what the "sum of primes" was supposed to be? Why does it produce 0 if the number wasn't prime?

    print('Number: {}'.format(num))
    print('Factors: {}'.format(factors))
    print('Factor count: {}'.format(len(factors)))
    print('Sum of factor: {}'.format(sum(factors)))
    print('Sum of numbers: {}'.format(sum(numbers)))
    print('Sum of Primes: {}'.format(num if len(factors) == 2 else 0))
    print(''.format(primes))

Wait a second ... what is that last print statement printing? ''.format(primes)? Did you have an argument to the format statement that didn't have a corresponding {} code???

Python 3.6+ now has something called an f-string, which allows you to interpolate values and expressions directly into the string, so you will never mismatch .format(*args) again!

    print(f'Number: {num}')
    print(f'Factors: {factors}')
    print(f'Factor count: {len(factors)}')
    print(f'Sum of factor: {sum(factors)}')
    print(f'Sum of numbers: {sum(numbers)}')
    print(f'Sum of Primes: {num if len(factors) == 2 else 0}')
    print()

Looping a Fixed Number of Times

def user_in(num):
    while True:
        if num <= 2:
            break
        num -= 1
        ...

This code wants to loop starting from num - 1, and go down and stop at 2. This is what for variable in range(): statements were meant for. Don't recreate for loops by using while True loops and modifying the loop index yourself:

def user_in(start):
    for num in range(start - 1, 2, -1):
        ...

Sum of all primes

print('... Sum of all primes: {} ...'.format(..., sum(flat_list) + x, ...))

What is that + x doing there? If I give as input the number 4, it computes the primes less than 4 to be [2, 3], and the sum to be 9! I'm pretty sure this is wrong.

Reworked Code

I've reworked the code a little bit, trying to reason out what you were actually trying to do. For example "Sum of primes" I implemented a running total of the prime numbers being generated. I also implemented the faster factorization method, I mentioned above, as a separate function. For good measure, I added a sum_up_to function for computing \$\sum_{i=1}^{n} i\$. Finally, the main function has been renamed to find_primes_up_to(), since that seems to be what it is doing, and the mainline code has been moved into a if __name__ == '__main__': guard, so the file can be imported into other files, and allows unit tests to be added.

import math

def factorize(num):
    if num == 1:
        return [1]

    limit = math.isqrt(num) + 1

    small = [1]
    large = [num]
    for i in range(2, limit):
        if num % i == 0:
            small.append(i)
            large.append(num // i)

    if small[-1] == large[-1]:
        large.pop()

    return small + large[::-1]

def sum_up_to(num):
    return sum(range(1, num + 1))

def find_primes_up_to(limit):
    sum_of_primes = 0
    primes = []

    for num in range(1, limit + 1):
        factors = factorize(num)

        print(f'Number: {num}')
        print(f'Factors: {factors}')
        print(f'Factor count: {len(factors)}')
        print(f'Sum 1 to {num}: {sum_up_to(num)}')

        if len(factors) == 2:
            primes.append(num)
            sum_of_primes += num
            print(f'Sum of primes: {sum_of_primes}')

        print()

    return primes

if __name__ == '__main__':
    limit = int(input("Enter upper limit: "))
    primes = find_primes_up_to(limit)
    print(f'Primes: {primes}')
    print(f'Sum of all primes: {sum(primes)}')
\$\endgroup\$
4
  • \$\begingroup\$ Thanks for the review. I appreciate the feedback on it. The code is going to be used for pattern recognition of primes and composite numbers. If have used the variable outside of the while loop to catch the results and use without needing to make it global. \$\endgroup\$
    – Barb
    Dec 23, 2019 at 14:16
  • \$\begingroup\$ To iterate over the factor list with the arguments <= 2 and != 1 is for simplicity of filtering the 1's out of the prime list. as 0, 1 are not primes and its easier to remove them before they are put in the list. With the printing statements I could of used a triple quote with format but it is just a rough start before making a more functional code with try and exceptions. I ideally am trying to make the code as short as possible. I will however use some of your ideas in respect to the separate functions \$\endgroup\$
    – Barb
    Dec 23, 2019 at 14:16
  • \$\begingroup\$ I purposely left the square root out because of the number 2.. Although it is a prime 2 is an irrational number so squaring it will return a float \$\endgroup\$
    – Barb
    Dec 23, 2019 at 14:22
  • 1
    \$\begingroup\$ Note: math.isqrt() is the integer square root. It is new in Python 3.8 \$\endgroup\$
    – AJNeufeld
    Dec 23, 2019 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.