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:
factors.append(i)
primelst =
for i in factors:
check = True
for j in range(2,i):
if i % j == 0:
check = False
if check == True:
primelst.append(i)
total = 0
for i in primelst:
total = total + i
return total - 1
print(sum_of_prime_factors(91))
def sum_of_prime_factors(n):
x = 0
for i in range(2, n + 1):
if n % i == 0:
if n == i:
return i
else:
y = sum_of_prime_factors(n // i)
if i != y:
return i + y
return y
print(sum_of_prime_factors(91))
[codebyte]
def sum_of_prime_factors(n):
primes =
for number in range(n+1):
start = 2
while number > start:
if number%start ==0:
break
start = start +1
if number == start:
if n%number ==0:
primes.append(number)
return sum(primes)
print(sum_of_prime_factors(91))
[codebyte]
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,
print(sum_of_prime_factors(96))
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)]:
prime.append(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
else:
break
return sum_prime
print(sum_of_prime_factors(60))