Hướng dẫn largest prime factor python

When substituting x in the get_large function with a large integer such as 600851475143 the program stalls and doesn't return a value. But, when substituting x with a smaller integer such as 20 it returns the result. How can I fix this?

Nội dung chính

• Source Code
• How do you find the highest factor in Python?
• How do you find the largest factor of a number?
• What is largest prime factor in Python?
• How do you factor a number in Python?

Nội dung chính

• Source Code
• How do you find the highest factor in Python?
• How do you find the largest factor of a number?
• What is largest prime factor in Python?
• How do you factor a number in Python?

factors = []  # create new empty list

def calc[x]:
    for n in range[1, x]:
        if x % n == 0:
            factors.append[n]  # if x is divisible by n append to factor list
    return factors

def get_large[x]:
    calc[x]  # call the returned values in factors list
    return calc[x][-1]  # return the last factor in the list

print["The largest factor is: " + str[get_large[600851475143]]]

mkrieger1

15.6k4 gold badges45 silver badges57 bronze badges

asked Jun 20, 2018 at 18:53

5

Here is mine. Note that factors is local to calc[] so we aren't constantly appending to the previous list.

Also note that get_large[] only has to call calc[] once. There is no reason to call it twice.

Finally, I replaced your algorithm in calc[] with one that should go substantially faster.

def calc[x]:
    factors = []
    i = 2
    while i < x:
        while x % i == 0:
            x /= i
            factors += [i]
        i += 1
    return factors

def get_large[x]:
    return calc[x][-1] #return the last factor in the list


print ["The largest factor is: " +str[get_large[600851475143]]]

Result, including timing:

$ time python3 x.py
The largest factor is: 1471

real    0m0.065s
user    0m0.020s
sys 0m0.004s

answered Jun 20, 2018 at 19:26

RobᵩRobᵩ

157k17 gold badges225 silver badges300 bronze badges

1

It's probably not broken, just taking a long time. Python is well known for being slow when running big for loops. I would recommend something like the following:

def calc[x]:
    n = 2
    factors = []
    while x != n:
        if x % n == 0:
            factors.append[n] #if x is divisible by n append to factor list
            x = x / n #this will safely and quickly reduce your big number
            n = 2 #then start back at the smallest potential factor
        else:
            n = n + 1
    return factors #This will return a list of all prime factors

def get_large[x]:
    bigFactor = x / calc[x][0]
    #The largest factor is just the original
    #number divided by its smallest prime factor
    return bigFactor

I used 2 as the smallest potential factor because using 1 would get us nowhere :]

answered Jun 20, 2018 at 19:24

2

if the number itself is not the largest factor, then why to loop till x, it can looped until x/2 .

answered Jul 24, 2018 at 4:00

nandynandy

811 silver badge3 bronze badges

[Edited]

import math

def get_large[x]:
    for n in range[2, math.ceil[math.sqrt[x]]]:
        if x % n == 0:
            return x / n
    return 1

print ["The largest factor is: " +str[get_large[600851475143]]]

Your code is too inefficient and so it takes forever to run for large numbers. The above is a more efficient version.

answered Jun 20, 2018 at 19:13

2

Source Code

# Python Program to find the factors of a number

# This function computes the factor of the argument passed
def print_factors[x]:
   print["The factors of",x,"are:"]
   for i in range[1, x + 1]:
       if x % i == 0:
           print[i]

num = 320

print_factors[num]

Output

The factors of 320 are:
1
2
4
5
8
10
16
20
32
40
64
80
160
320

Note: To find the factors of another number, change the value of num.

In this program, the number whose factor is to be found is stored in num, which is passed to the print_factors[] function. This value is assigned to the variable x in print_factors[].

In the function, we use the for loop to iterate from i equal to x. If x is perfectly divisible by i, it's a factor of x.

How do you find the highest factor in Python?

Problem statement. Given a positive integer n. ... .

Approach..

Example. Live Demo import math def maxPrimeFactor[n]: # number must be even while n % 2 == 0: max_Prime = 2 n /= 1 # number must be odd for i in range[3, int[math. ... .

Output. ... .

Conclusion..

How do you find the largest factor of a number?

The greatest common factor is the greatest factor that divides both numbers. To find the greatest common factor, first list the prime factors of each number. 18 and 24 share one 2 and one 3 in common. We multiply them to get the GCF, so 2 * 3 = 6 is the GCF of 18 and 24.

What is largest prime factor in Python?

Python Challenges - 1: Exercise-35 with Solution The prime factors of 330 are 2, 3, 5 and 11. Therefore 11 is the largest prime factor of 330.

How do you factor a number in Python?

Note: To find the factors of another number, change the value of num . In this program, the number whose factor is to be found is stored in num , which is passed to the print_factors[] function. This value is assigned to the variable x in print_factors[] .