Python Challenge - Sum of Prime Factors

Ah thank you much. I now understand.

1 Like

Now the question is, ‘why did it work?’ This is an edge case that is a necessary forensic investigation concern.

1 Like

Oh. yes, because of count==2 condition since 1 only can be divided by its own without remainder, therefore, count = 1 for x value of 1.

1 Like

Not the cleanest but the first code i got to function properly

def sum_of_prime_factors(n):
lst = list(range(1,n+1))
factors =
for i in lst:
if n % i == 0:
primelst =
for i in factors:
check = True
for j in range(2,i):
if i % j == 0:
check = False
if check == True:
total = 0
for i in primelst:
total = total + i
return total - 1


def sum_of_prime_factors(n):
x = 0
for i in range(2, n + 1):
if n % i == 0:
if n == i:
return i
y = sum_of_prime_factors(n // i)
if i != y:
return i + y
return y


def sum_of_prime_factors(n):
primes =
for number in range(n+1):
start = 2
while number > start:
if number%start ==0:
start = start +1
if number == start:
if n%number ==0:
return sum(primes)


def sum_of_prime_factors(n): sum = 0 for num in range(2, n + 1): for i in range(2, num): if num%i == 0: break else: if n%num == 0: sum += num return(sum) print(sum_of_prime_factors(91))

Hard to explain what I did. First, I eliminating any non-prime numbers in the second for loop. If it is a prime number, check if our number (91) is divisible by this prime number.

def isPrime(a): if a <= 1: return False for n in list(range(2, a)): if a % n == 0: return False return True def primesList(b): #b is a list of numbers primesList = [] for n in b: if isPrime(n): primesList.append(n) return primesList #returns a list of prime numbers from the orginal list def findFactors(a): #a is an integer factors = [] for x in list(range(1, a + 1)): if a % x == 0: factors.append(x) return factors #returns a list of factors def sum_of_prime_factors(n): factors = findFactors(n) primes = primesList(factors) return sum(primes) print(sum_of_prime_factors(10))
def sum_of_prime_factors(n): #note that every prime number that n is divisible through is a prime factor c = 0 #counter for primefactors for i in range (2, n + 1): #iteration through all numbers up to n that could be prime if n % i == 0: #test if i|n for j in range (2, i): #iteration to test if i is prime if i % j == 0: #test if j|i break #if j|i, i is not prime, so break else: c += i #if i is prime, add to counter return c print(sum_of_prime_factors(100))
def sum_of_prime_factors(n): primes = [] prime_factors = [] for x in range(2,n+1): for y in range (2,x): if x%y == 0: break else: primes.append(x) for x in primes: if n%x == 0: prime_factors.append(x) return sum(prime_factors) print(sum_of_prime_factors(91))
def sum_of_prime_factors(n): sum=0 for i in range(2, n+1): if n % i ==0: for x in range(2, i): if i % x ==0: break else: sum+=i return sum print(sum_of_prime_factors(91))
def sum_of_prime_factors(n): # Write your code here # Helper function is_prime returns whether a number is prime def is_prime(m): for i in range(2,m): if m%i == 0: return False return True # Find all the prime numbers between 2 and n list_of_primes = [] for i in range(2, n+1): if is_prime(i): list_of_primes.append(i) # Find factors of n list_of_factors = [] for i in list_of_primes: if n%i == 0: list_of_factors.append(i) # Return sum of factors return sum(list_of_factors) print(sum_of_prime_factors(91))
def sum_of_prime_factors(n): # Write your code here # Sum of prime factors for n sum_factors = 0 half_n = int(n/2) p_number = 2 # Function to know if an integer is a prime number or not def is_a_prime_number(num): prime = True sqrt_n = int(num**0.5) number = 2 while number <= sqrt_n: if num % number == 0: prime = False break number += 1 return prime # If n is a prime number, we just send n as the sum because it has only 1 and itself as prime factors if is_a_prime_number(n) == True: sum_factors = n #If not, we have to retrieve only the prime numbers else: while p_number <= half_n: if (n % p_number == 0) and (is_a_prime_number(p_number) == True): sum_factors += p_number p_number += 1 return sum_factors print(sum_of_prime_factors(91)) #20
def sum_of_prime_factors(n): # Write your code here '''start = 2 ans = 0 while start <= n: isprime = True for i in range(2,start): if start %i == 0: isprime = False break if isprime == True and n%start == 0: ans += start start += 1 if n == 1: return 0 else: return ans''' # Make more Efficient if n == 1: return 0 ans = 0 L = [] for i in range(2,n//2 + 1): if n % i == 0: isprime = True for j in L: if i%j == 0: isprime = False break if isprime == True: L.append(i) ans += i if n > 1 and ans == 0: return n else: return ans print(sum_of_prime_factors(91))
1 Like

Gives the correct answer for this,


which is what matters most, before any consideration is given to efficiency. When efficiency really matters you’ll have by then explored optimization, which approaches the concerns from several directions. For now, keep up the good work at getting your program to return trustworthy results.

Who said that perfection is the enemy of good enough?

To check if a factor is prime or not, the conventional method is to test out divisibility with all preceding numbers of the factor. This has O(n^2) complexity.
In my method, for each factor i, I’ve collected all previously known(less than i) prime factors of n into a list and only checked divisibility against all elements of the list.
This drastically reduces the complexity to O(n*p(n)) where p(n) is the number of prime factors of n

1 Like

Big-O complexity seeks out the worst case, not the best, meaning p(n) is treated as n despite the optimization so O(N) is still O(n^2).

How is p(n) approximated as O(n)?
Consider the examples:
30 = 2 x 3 x 5
p(30) = 3
2310 = 2x3x5x7x11
p(2310) = 5
As n gets larger, p(n) << n
U might say,(Im not 100% sure) that p(n) has theta(log n) complexity,
giving an overall complexity of Theta(n log n)

1 Like

It is easy to argue that it is not O(n^2), but that is the worst case when p(n) us treated as n. One won’t dispute that the optimized code is closer to O(n log n), so that is acceptable, and perhaps in this case it is the worst case. You have a point. We could use another opinion, to be fair.

def sum_of_prime_factors(n):

  def prime_finder(n):
    prime = []
    for a in range(2, n+1):
      if 0 not in [a%b for b in range(2, a)]:
    return prime

  sum_prime = 0
  primes = prime_finder(n)
  for p in primes:
    prod = n
    if prod%p == 0:
      prod = n/p
      sum_prime += p
      while True:
        if prod%p == 0:
          prod = prod/p
  return sum_prime