CODEWITHSUNDEEP
algorithmpython-3.x
mskr
mskr

Reputation: 3

Beginner (Python 3.6.1): Why isn't this script working?

Keep in mind I've only started learning Python (first language) a few days back.

I'm trying to find the greatest prime factor of a given (and potentially big) integer 'a'. I start by defining a function prime(n) that checks whether an integer 'n' is prime or not. I then find factors 'n' of 'a' from biggest to smallest and check each with prime(n). If a prime n is found, it is printed out and I use break to end the process. If n=1 is the only prime factor found, then 'a' is prime, and so its greatest prime factor is itself.

This script fails completely. The variable n_prime goes back to whatever value I first give it even after prime(n) should change it to either True or False. If I start with it being None, after prime(n), it always remain None.

I hope it isn't too messy, and that there aren't too many issues with my code.

def prime(n): 
if n == 1:
    n_prime = False

if n == 2:
    n_prime = True

if n == 3:
    n_prime = True

if n % 2 == 0 and n_prime != True:
    n_prime = False

else:
    for i in range(3, n, 2):
        if i != n:
            if n % i == 0:
                n_prime = False
                break
        else:
            n_prime = True



n_prime = None
a = int(input())

for n in range (a-1, 1, -1):

     if a % n == 0:
          prime(n)
          if n_prime==True:
               if n != 1:
                   print(n, ' is the greatest prime factor of ', a)
                   break
               else:
                   print(a, 'is the greatest prime factor of ', a)
                   break

Upvotes: 0

Views: 91

Answers (1)

Blckknght
Blckknght

Reputation: 104722

Your code doesn't work because your prime function doesn't modify the global variable n_prime the way it looks like you're expecting it to. You could make it work by adding a global statement at the top of the function: global n_prime. But that's not the best approach. Modifying global variables from within a function loses much of the benefits a function gives.

A better way is to return the value you want to use in the calling code:

def prime(n): 
    if n == 2 or n == 3: # We can reorder and combine some of the conditions up here
        return True # return instead of trying to assign to the global variable!

    if n == 1 or n % 2 == 0:
        return False

    for i in range(3, n, 2): # The end value of a range is not used in the iteration.
        if n % i == 0:       # So the logic that was checking `i != n` is unnecessary.
            return False

    return True  # if the loop finished without returning, we know our value is prime

Here's how I'd use that function in the greatest prime factor algorithm you showed:

a = int(input())

for n in range (a-1, 1, -1): # This loop stops at 2. It doesn't ever reach 1, but that's OK!
    if a % n == 0 and prime(n): # Test the return value from the function here!
        print(n, ' is the greatest prime factor of ', a)
        break
else: # This else block is attached to the loop. It runs only if the loop didn't `break`.
    print(a, 'is the greatest prime factor of ', a)

Note that it's not necessary to compare a boolean value to another one (with e.g. n_prime == True. Just use the boolean value directly in an if (or with a boolean operator like and or or).

I'd also note that you could get rid of the special case at the end (for when a is prime), and simply change the loop to start with a instead of a-1. Since you check if n is prime after seeing that it's a divisor, this will only print out the message if the prime function confirms that a has no factors (other than itself and one).

Upvotes: 2

Related Questions