0
\$\begingroup\$

Take input n1 and n2 and check if they have the same greatest factor. If they do, print that factor. If they don't, print "No".

example:
input:
6
9
output:
3

input:
15
27
output:
No

n1=int(input())
n2=int(input())
l1=[]
l2=[]
for i in range(1,n1):
    if n1%i==0:
        l1.append(i)
        l1.sort(reverse=True)
cf1=l1[0]
for j in range(1,n2):
    if n2%j==0:
        l2.append(j)
        l2.sort(reverse=True)
cf2=l2[0]
if cf1==cf2:
    print(cf1)
else:
    print("No")
\$\endgroup\$
8
  • \$\begingroup\$ Your code is not finding the greatest common factor. It's finding if the greatest factors of the two numbers are equal. The usual way to find the greatest common factor is the Euclidean algorithm. \$\endgroup\$
    – Teepeemm
    Commented Oct 23, 2021 at 14:20
  • \$\begingroup\$ The GCF of 15 and 27 should be 3. I've voted to close this question, since we only review code that is working correctly on this site. \$\endgroup\$ Commented Oct 23, 2021 at 15:40
  • \$\begingroup\$ @200_success no, we have to check if the greatest is same or not. for 15 it is 5 and for 27 it is 9 so not equal \$\endgroup\$
    – students
    Commented Oct 23, 2021 at 17:04
  • \$\begingroup\$ @Teepeemm how to use euclidean algorithm? \$\endgroup\$
    – students
    Commented Oct 23, 2021 at 17:05
  • 1
    \$\begingroup\$ (I'm somewhat ill at ease with the problem statement not explicitly excluding a natural number as its own factor.) \$\endgroup\$
    – greybeard
    Commented Oct 23, 2021 at 22:37

3 Answers 3

0
\$\begingroup\$

At any point, 1 is always common factor of any two numbers. Your code works perfectly. But if you want to write a shorter code, check the condition if both numbers are divisible by any number using for loop going from range 2 (1 is always factor) to min of both numbers. Take a new variable f which is False initially. If the condition is satisfied i.e. if both nos are divisible by a no, change f to True. Then, out of the loop, write an if condition, if f==True then print the number or else the condition was never satisfied and f is False and print "no". Your code:

n1=int(input("Enter n1"))
n2=int(input("Enter n2"))
f=False
for i in range(2,min([n1,n2])):
    if n1%i==0 and n2%i==0:
        g=i
        f=True
if f:
    print(g)
else:
    print("no")
\$\endgroup\$
2
  • 2
    \$\begingroup\$ This is a (slow) implementation of finding the greatest common factor, but that's not what OP's code dos. \$\endgroup\$
    – Teepeemm
    Commented Oct 23, 2021 at 14:18
  • \$\begingroup\$ (Ignoring not checking factors higher than any common ones: How about for i in range(min([n1,n2])//2, 1, -1): ?) \$\endgroup\$
    – greybeard
    Commented Oct 24, 2021 at 0:08
1
\$\begingroup\$

Quick and easy changes:

  • input should prompt what it's asking for.
  • You want to encapsulate what you're doing into a function, but the function should just return, not print. But it's strange for a function to sometimes return a string and sometimes a number, so I've made it only return a number, and saved switching to "No" for the main thread to decide.
  • You should document what you're doing and why. Since there's been some confusion about the greatest common factor, you should definitely document that this isn't that. Type hints are also nice. I've also included some doctest entries, so that you could run python -m doctest -v myscript.py and double check that it's working.
  • Use an if __name__ == '__main__' guard
  • The only point of l1 is to get the first number. We can skip the reversing and just get the last number: cf1=l1[-1].

A much better change comes from realizing that factors come in pairs (with a square root paired with itself). This means that the greatest factor pairs with the least factor greater than 1:
cf1 = n1/next( n for n in range(2,n1+1) if n1%n==0 )
We could do the same thing for cf2, which would make the function symmetric and easier to understand. But if we're desperate for that last performance boost, we can do a bit better:

If they have a common greatest factor, then it will be the greatest common factor. The Euclidean algorithm will very quickly find this value. The only thing that could mess things up would be if there is some other factor between cf and n. That could be a lot of numbers to check, but we can do the pairing trick again, and look for other numbers between 1 and n/cf. If there's a factor there, then there is a greater factor than the greatest common factor, and they don't have a common greatest factor.

def commonGreatestFactor(n1:int,n2:int) -> int:
    '''
    Finds if the greatest factor of each number is the same, and returns it.
    This is not the greatest common factor
    (although if they have the same greatest factor, then it is equal to the gcf).
    If they do not share the same greatest factor, this returns 0.
    
    >>> commonGreatestFactor(3,6)
    0
    >>> commonGreatestFactor(6,9)
    3
    >>> commonGreatestFactor(12,18)
    0
    >>> commonGreatestFactor(15,27)
    0
    '''
    gcf,other = n1,n2
    while other:
        gcf,other = other,gcf%other
    if min(n1,n2)==gcf<max(n1,n2):
        return 0
    # if there's a factor of n1 between 1 and n1/gcf,
    # then the gcf is not the greatest factor of n1
    if next( (n for n in range(2,n1//gcf) if n1%n==0) , 0 ):
        return 0
    if next( (n for n in range(2,n2//gcf) if n2%n==0) , 0 ):
        return 0
    return gcf

if __name__ == '__main__':
    n1=int(input('First number: '))
    n2=int(input('Second number: '))
    result = commonGreatestFactor(n1,n2)
    if result:
        print(result)
    else:
        print("No")
\$\endgroup\$
4
  • \$\begingroup\$ Let's try some more inputs - a) 6, 3 b) 12, 18. \$\endgroup\$
    – greybeard
    Commented Oct 23, 2021 at 21:30
  • \$\begingroup\$ @greybeard My comment was using n for n1, not for the index of the range (which wasn't a good idea on my part). It was getting (12,18)->0, as it should, but it was missing (3,6)->0, which I've fixed. Thanks. \$\endgroup\$
    – Teepeemm
    Commented Oct 24, 2021 at 0:35
  • \$\begingroup\$ (if min(n1,n2)==gcf, gcf<max(n1,n2)n1 != n2: if n1 != n2 and min(n1, n2) == gcf:) I'm not quite sure what the result of a) should be - but shouldn't it be consistent with c) 6, 6? c) seems to call for 3 (exclude n1/n2) or 6 (allow). (similarly for d) 2, 3: is "the other trivial factor" allowed? students' code does.) (Don't quite know what I was thinking of suggesting b) (missed 9 as a divisor).) There's math.gcd(). \$\endgroup\$
    – greybeard
    Commented Oct 24, 2021 at 8:52
  • \$\begingroup\$ Seeing several places where it would be great to know n1 was no smaller than n2, I might assure that upfront (possibly handling n1==n2 as a special case). Then, I could use (n for n in range(2, n2//gcf) if n1%n==0 or n2%n==0) followed by range(n2//gcf, n1//gcf) if n1%n==0. \$\endgroup\$
    – greybeard
    Commented Oct 24, 2021 at 8:55
0
\$\begingroup\$

"The sort()s" would work just fine called once each - after the loops.
Instead of l1.sort(reverse=True), you could just use l1 = list(reversed([1, 2])). Or omit permuting the lists and just pick the highest factor:
factor1 = l1[-1]
(Building the lists using
l1.insert(0, trial_divisor) followed by factor1 = l1[0] is worse.)

But when wanting greatest factors, only, why accumulate complete lists?

def greatest_factor(n):
    """ Given a natural number n, return its greatest factor below n."""
    if n % 2 == 0:
        return n // 2
    for trial_divisor in range(3, int(math.sqrt(n)) + 1, 2):
        if n % trial_divisor == 0:
            return n // trial_divisor
    return 1

(Consider defining smallest_factor() (exceeding 1) and using that for greatest_factor().)

(For a sane way to check for a common greatest factor as defined in the problem statement, Teepeemm's answer's first revision just needs a bit of tying up loose ends.)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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