[Challenge] Sum of Prime Factors

challenge

#1

Code Challenge, April 5th 2017

Every two weeks, we feature the type of brain-teasing question that might be asked in a full-stack developer's job interview.

For this week's challenge:

Write a function that finds the sum of all prime factors of a given number, n.

Try to write your function without using trial division!

Scroll down and reply to this thread with your code to participate!


Extra Credit

Intermediate Difficulty

If you'd like to go a step further:

Write a function that finds the sum of each unique prime factor of a given number, n. For example, 3 is the only prime factor of 9.

Advanced Difficulty

For a final, more advanced challenge, your code should run in sub-linear time (find out what we mean by reading about Big O notation and complexity here and here). There's also an old (and thus unsupported) Codecademy course on Big O here (thanks @mindful_coder).


How to participate

We featured the best submissions entered in the opening few days of this challenge here, but do feel free to continue to post your answers below!

Happy coding!


The fine print:
* Remember, the point of code challenges like these is to test and stretch yourself with an unusual problem, so don't be dissuaded if you find it difficult or don't know where to start! Start with Googling, but see if you can find out how to think about the problem and what tools you need to solve it, but don't just go looking for the solution itself. This way, it'll be a better learning exercise for you - developers can't always find and copy "the right answer" online, which is why questions like these are used in developer job interviews!
* Do you have a code challenge to share with other users? Let us know! Make a new topic with [Challenge] in the title to open a challenge, maybe we'll even feature it in our next newsletter!


Essential Information on Code Challenges
#2

There it goes! My first coding challenge :stuck_out_tongue: I don't expect it being good but I started coding recently, let's see.

from math import sqrt
#this function will sum the primes found:
def sum(list):
  values=0
  for i in list:
    values+=i
  print values
  return values
#This function will find the primes in a number n:
primes=[]
def findprimes(n):
  while n%2==0:                 #if our number n is even it will append a 2 factor and it will be divided until we get an odd number.
    primes.append(2) 
    n=n/2
  i=3
  while i<=sqrt(n):             #The tiniest prime factor of a number n must be equal or less than its square root. We add them while
    while n%i==0:               #dividing it, so it will append every factor until we have the last factor (irreducible).
      primes.append(i)
      n=n/i
    i+=2
  if n>2:                          #Here we append the last factor.
    primes.append(n)

findprimes(3072)
print "The list of primes is: "
print primes
print "And their sum is: "
+sum(primes)
#the next function filters the repeated primes:
def sumdifferentprimes(list):
  newlist=[]
  for item in list:            #Basically it adds a number unless it was already added.
    if item not in newlist:
      newlist.append(item)
  newsum=0
  for i in newlist:
    newsum+=i
  print newlist
  print newsum
  return newsum
print "The list with no repetitions and the sum:"
sumdifferentprimes(primes)

#I'm new at programming and I found this challenge pretty fun, I hope this is fine enough! Sadly I couldn't apply the Advanced condition.

#3

There's an archived Codecademy Big O course if you want to find out a bit more about algorithmic efficiency. The course is JavaScript-based, but hopefully some of you will find it an interesting diversion :slight_smile:

https://www.codecademy.com/courses/big-o/0/1

As it's an archived course, there's no official support, but you might want to take a look at the old forum section for the course:

https://www.codecademy.com/forums/big-o


#4

Oh thanks! I have a good understanding of JavaScript so it shouldn't be a problem. Let's see what I can learn from that course. Thanks again!


#5

#include <stdio.h>
#include <math.h>
 
// A function to print all prime factors of a given number n
void primeFactors(int numberIn)
{
    // Print the number of 2s that divide n
    while (numberIn%2 == 0)
    {
        printf("%d ", 2);
        numberIn = numberIn/2;
    }
 
    // n must be odd at this point.  So we can skip 
    // one element (Note i = i +2)
    for (int i = 3; i <= sqrt(numberIn); i = i+2)
    {
        // While i divides n, print i and divide n
        while (numberIn%i == 0)
        {
            printf("%d ", i);
            numberIn = numberIn/i;
        }
    }
 
    // This condition is to handle the case when n 
    // is a prime number greater than 2
    if (numberIn > 2)
        printf ("%d ", numberIn);
}
 
/* Driver program to test above function */
int main()
{
    int numberIn = 315;
    primeFactors(numberIn);
    return 0;
}

#6

Hi there!

here are my solutions for the sum of prime factors and the sum of unique prime factors:

def sum_of_prime_factors(n):
	divisor = 2 #starting with 2, as it is the smallest prime number
	sum = 0 #at the beginning we dont have anything added up, therefore 0
	while divisor <= n/2: # as 2 is the smallest possible divisor, we only need to check for numbers up to n/2. If this value is reached, we can skip and assume, that the rest of n will be our last prime factor.
		if(n%divisor == 0): #if our divisor divides n without rest, it is a prime factor of n.
			n = n/divisor #therefore we devide n by our divisor
			sum = sum + divisor # and sum it up
		else: #if is does not divide, we check the next higher number
			divisor = divisor + 1

	return sum+n #add up our last prime factor here
	# it is no problem here to check for numbers not being primes themselves, as we start with the smallest primes we will have splitted the number into something that cant contain any mulitples of those. 

#for uniques it is kind of the same code, except that we remember, with which number we last devided our input and act accordingly
def sum_of_unique_prime_factors(n):
	divisor = 2
	sum = 0
	lastDivisor = 0 # in this case, we also have to know, what our last divisor was, so we can skip it for sum-computation if it occurs multiple times
	while divisor <= n/2:
		if((n%divisor) == 0):
			n = n/divisor
			if(divisor != lastDivisor): # the check for non-unique divisors happens here, if it occured multiple times, it will not be summed up another time
				lastDivisor = divisor
				sum = sum + divisor
		else: 
			divisor = divisor + 1

	return sum if n == lastDivisor else sum+n #add up our last prime factor here, if it's another unique one

for optimization it would be great to have a precomputed list of primes, instead of iterating through all numbers including the multiples of primes
if anything isn't clear, feel free to ask :slight_smile:


#7

def is_prime(num):
  for i in range(2,num):
    if num%i==0:
      return False
  return True

def sumPrimeFactors(num):
  sum=0
  primeSums = []
  for i in range(2,num-1):
    if is_divisible(i,num) and is_prime(i):
      sum+=i
      primeSums.append(i)
  print("The prime factors of",num,"are:",primeSums)
  print("The sum of the prime factors of",num,"is",sum)

#8

from math import *

def sum_prime_factors(n):
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return i + sum_prime_factors(n/i)
    return n

def sum_unique_prime_factors(n):
	def unique_prime_factors(n):
		for i in range(2, int(sqrt(n)) + 1):
			if n % i == 0:
				return set([i]).union(unique_prime_factors(n/i))
		return set([n])
	return sum(unique_prime_factors(n))

#9

This is my attempt: it leverages the Sieve of Eratosthenes method. No arithmetic divisions!! The method of the SoE is easily available elsewhere.

I agree it's a really inefficient use of memory: I also have a class that implements a long array of booleans in an array of integers, but it's a bit long for just the simple answer here. Let me know if you want to see that too!!

#! /usr/bin/python3

# get the value to be looked for from the command line
# no type checking here!
import sys
TARGET=int(sys.argv[1])

# set up an array of booleans up to and including the TARGET
sieve = [False] * ( TARGET + 1 )

# in classic Erathosthenes, cross out all the non primes
# note: if the sieve lands on the TARGET, then it's a factor
# so remember it.
primes = []
number = 2

# we have to go all the way up to the target in case
# it's a prime itself!
while number <= TARGET:

    for n in range(number, TARGET+1, number): 
        # mark all the multiples of number because they're
        # obviously not prime
        sieve[n] = True
        # if it matches the TARGET, then it's a factor
        if n == TARGET: primes.append(number)

    # move on to the next prime number
    while (number <= TARGET) and (sieve[number]) == True:
        number += 1

# Here is the answer
print(primes)
print(sum(primes))

Tim F


#10

This is my code. It's written in C++. It has 3 functions and the main().

The prime factors are stored in an array of integers which were checked befor if they are prime.
Then another recursive function calculates the sum of the array and it is printed to the console.

// Write a function that finds the sum of all
// prime factors of a given number, n.
//

#include "stdafx.h"
using namespace std;
int arr[1000000];

// function checks if the number is prime
int isPrime(int b)
{
	for (int i = 1; i * i <= b; i++)
	{
		if (b % i == 0 && i != 1) return 0;
	}

	return 1;
}

// calculates the sum of the array with factors
int sum(int arrl)
{

	if (arrl == 0) return 0;
	else return sum(arrl - 1) + arr[arrl - 1];
}

// identifies prime factors and stores them into an array
int primeFactors(int n, int arrl)
{
	for (int i = 2; i < n; i++)
	{
		if (n % i == 0 && isPrime(i))
		{
			arr[arrl++] = i;
		}
	}


	return sum(arrl);
}




int main()
{
	int arrl = 0, n, sum1;

	// input
	cin >> n;

	// Functions are called
	sum1 = primeFactors(n, arrl);
	cout << sum1 << endl;
	system("pause");
    return 0;
}

here's another way to do it:
(This time it prints the sum of all prime factors even if the are repetited)

#include "stdafx.h"
using namespace std;

// function which calcuates the sum of the prime factors
// a variable 'add' which stores the sum
// and 'n' the input number
int factorSum(int add, int n)
{
	for (int i = 2; i <= n; i++)
	{
		while (n % i == 0)
		{
			// divide and add the value to 'add'
			n /= i;
			add += i;
		}
	}

	// return the sum
	return add;
}


int main()
{
	int sum, add = 0, n;

	cin >> n;
	sum = factorSum(add, n);
	cout << sum << endl;

	system("pause");
    return 0;
}

I've also designed a version of it in PYTHON.
I'm surprised that it's much shorter.

# n the number, sum must be 0 so we can add factors to it
def factors_sum(n, sum = 0):
    # every number smaller than n+1 (if n is prime) 
    for i in range(2, n + 1):
        # check if it can be divide by i
        while n % i == 0:
            # divide
            n /= i
            # add to sum
            sum += i
    # return their sum
    return sum

#11

Here is my attempt in Python, sum of factors and of unique factors.
Could not quite avoid the trial division though )-;

import math

def is_prime(n):
	for i in range(2, int(math.sqrt(n))+1):
   		if n % i == 0:
   			return False  #composite
	return True #prime


def prime_factors(p):
	result = []
	
	if p == 1:
		result.append(1) #avoid looping forever
		return result

	while p%2 == 0: #not included in range step
		result.append(2)
		p = p/2

	for i in range(3, p+1, 2): #no need to test even numbers
		if is_prime(i):
			while p%i == 0:
				result.append(i)
				p = p/i
		if p == 1: #no more factors to find
			break
	
	if len(result) == 0: #p is prime
		result.append(p)
	
	return result

def sum_of_factors(p):
	return sum(prime_factors(p))

def sum_of_unique_factors(p): 
	return sum(list(set(prime_factors(p))))

#12

Rereading the problem and looking at other submissions, there is a way of listing all the prime factors, not just unique ones. Here is revised code:

#! /usr/bin/python3

# get the value to be looked for from the command line
# no type checking here!
import sys
TARGET=int(sys.argv[1])

# set up an array of booleans up to and including the TARGET
sieve = [False] * ( TARGET + 1 )

# in classic Erathosthenes, cross out all the non primes
# note: if the sieve lands on the TARGET, then it's a factor
# so remember it.
primes = []
number = 2
# need a sacrificial copy of the target in order to do sequential divisions
whatsLeft = TARGET

# we have to go all the way up to the target in case
# it's a prime itself!
while number <= TARGET:

    for n in range(number, TARGET+1, number): 
        # mark all the multiples of number because they're
        # obviously not prime
        sieve[n] = True
        # if it matches the TARGET, then it's a factor
        if n == TARGET:
            # add an element to the primes for each time
            # number divides into the target
            while whatsLeft % number == 0:
                primes.append(number)
                whatsLeft = whatsLeft / number
            # we can short circuit the rest if we've found all the factors
            if whatsLeft == 1: 
                number = TARGET+1
                break

    # move on to the next prime number
    while (number <= TARGET) and (sieve[number]) == True:
        number += 1

# Here is the answer
print(primes)
print(sum(set(primes)))

This is my first attempt at a discuss challenge, sorry for having to have more than one go!

Tim F


#13

Here's my take on the challenge :slight_smile:
Please feel free to tell me ways to optimise my code/more efficient ways of getting the same result

#sum of n's unique prime factors

n = input("Choose a positive integer greater than 1:")#user input of a single positive integer
b = int(n) #turning the input into a integer type
divisor = 2 #starting the divisor variable at 2 because that's the lowest prime factor possible
prime_factors = [] #list of all the prime factors of n
pf_sum = 0 #initializing the sum of n's prime factors at 0

if b == 1:
    print()
    print('The number 1 is called a unit. It has no prime factors and is neither prime nor composite.') #output in case user inputs 1
else:
    while b > 1: #loop to be repeated while b is higher than 1
        if b % divisor == 0: 
            prime_factors.append(divisor) #if b/divisor 's remainder is 0 then divisor will be added to the prime_factors list as a prime factor of n
            b = b / divisor #lower b to the value of b/divisor to make sure the prime factorization doesn't repeat itself
        else:
            divisor += 1 #in case the divisor wasn't a prime factor then we add 1 to the current divisor

'''print(prime_factors) #debugging'''

if int(n) != 1:
    prime_factors = set(prime_factors) #making a new list of prime_factors composed only by unique prime factors of n
    for num in prime_factors: #a loop to execute the sum of all of n's unique prime factors
        pf_sum += num
    print()
    print('{}\'s prime factors are {} and its unique prime factors\' sum is {}.'.format(n, prime_factors, pf_sum)) #final output

#14

Here's my attempt. It's a very "off the cuff" approach; I'm not familiar with any advanced mathematical concepts related to prime numbers... but I've been exposed to them now, thanks to this challenge!

I've outlined my thought process in my comments, to the best of my ability on a late night, at least!

Admittedly, my code is a bit bloated for the challenge. And there are probably some blocks that would be better-served as functions. Nonetheless, it has worked with a good quantity of random test numbers.

I structured it as a loop, so that a user can repeatedly enter numbers, until '0' is entered, without having to rerun the script.

I had to learn basic Python for this; it was a fun experience. I'm happy to have any positive or constructive feedback. :slight_smile:

Thanks for looking!

Use it on repl.it
(I'm new to this system, and I couldn't figure out how to embed the repl.it like the user above. Adding the embed script did nothing. A pro-tip on that would be great!)

# ***THOUGHTS***
# The approach used in this solution admittedly causes iterations with factors that are not prime.
# I should go back sometime and see if there is a performance gain or loss by checking whether a factor is prime before attempting the modulus operation.
#   My "sniff test" result is that it would (slightly) decrease performance in checking if the factor is a prime number, because multiple operations would be performed for each candidate factor before performing the modulus check.
#   As written, all potential odd factors are checked.  But they are only processed once if they are not a prime factor of the input number.
#
# There are some chunks of code that would be better served as functions... perhaps for v2!
#
# I'm sure there are some inconsistencies or deviations from Python conventions.  Please forgive them; this is my first attempt at Python.
#
# TODO: Add a try block to check for an integer input

# Will need square root & floor functions
import math

HEADER_PRIME = "PRIME FACTORS"
HEADER_UNIQUE_PRIME = "UNIQUE PRIME FACTORS"
HEADER_BOTH = "PRIME & UNIQUE PRIME FACTORS"

def displayFactors(header, factors_array, sum_of_factors):
    print("\n{}\n{}\nSum = {}\n".format(header, factors_array, sum_of_factors))
    

# Place all logic in an outer loop,
#   in order to continue entering numbers
#   without having to run the script each time.
# This loop will continue until 0 is entered.

while True:
    # Allow the user to enter a number to be factored
    number = int(input("Enter a number (0 = Exit)\n>"))
    
    # Exit the script if 0 was entered
    if number == 0:
        print("Exiting...")
        break
    # Display a special message if 1-3 was entered,
    #   because these numbers are prime numbers,
    #   and it is mathematically impossible for them to have another prime factor > 1
    elif number <= 3:
        print("{} is a prime number\n".format(number))
        displayFactors(HEADER_BOTH, [number], number)
        continue
    
    # The largest possible factor for any number is the square root of that number.
    # Since we're only considering prime integers, the factor should be floored.
    max_factor = math.floor(math.sqrt(number))
    
    print("Square root of {} is {}".format(number, math.sqrt(number)))
    
    # By definition, an even number larger than 2 cannot be a prime factor.
    # If the resulting max_factor value is even, subtract 1 from max_factor.
    #   The exception to this is a max_factor of 2, so it must also be checked as a condition
    #
    # max_factor will then represents the largest potential prime factor.
    if (max_factor % 2) == 0 and max_factor != 2:
        print("By definition, an even number higher than 2 cannot be a prime factor.")
        max_factor -= 1
    
    print("Therefore, the largest integer factor required for iteration is {}".format(max_factor))

    # Stop the console to view summary information before iterating over factors
    stop = input("[Press ENTER to continue...]")
    
    # Initialize or reset a list in which identified prime factors can be placed,
    #   for summary output after iterations are complete
    prime_factors = []
    
    
    # Helper function to iterate through each factor
    def checkFactor(dividend, divisor):
        while (dividend % divisor) == 0:
            prime_factors.append(divisor)
            print("{} / {} = {}".format(
                    dividend, divisor, dividend / divisor))
            dividend = dividend / divisor
        return dividend
    
    print("\nSHOWING WORK...")
    # Set the initial factor to the smallest possible prime factor,
    #   (excluding 1, because it has already been accounted for)
    factor = 2
    print("\nFactor is", factor)

    
    # 2 is a special case -- the only even prime number,
    #   so it must be checked before entering the main loop.
    number = checkFactor(number, factor)

        
    # Update factor to the next prime factor (3),
    #   unless max_factor <= 2
    # After this, it will increment within the while loop
    if max_factor > 2:
        factor = 3
        print("\nFactor updated to {}".format(factor))
    
    
    # The loop must continue until the value of 'number' has been reduced to 1
    # or the factor is > max_factor
    while number > 1:
        # If the number is evenly divisible by the current factor,
        # then it is a prime factor and should be added to the prime_factors list.
        # This check should repeated until the number is no longer divisible by the current factor.
        while (number % factor) == 0:
            number = checkFactor(number, factor)
            
        # If the current factor is greater than the max_factor,
        #   then either all prime factors have been identified in the loop
        #   or the final prime factor is the indivisible number value
        #
        # Check to see if the factor still needs to be updated
        if factor < max_factor:
            # This is checked by the while loop, 
            # but placing a check here allows for informational messages.
            #
            # Not needed for core functionality
            if number == 1:
                print("ALL FACTORS FOUND.  Exiting loop...\n")
                break
            
            # Since 2 has already been checked, 
            #   and the factor value is at least 3 at this point,
            #   every potential prime factor will be an odd number.
            #
            # Add 2 to increment to next odd factor.
            factor += 2
            print("\nFactor updated to {}".format(int(factor)))
        else:
            print("MAX FACTOR REACHED.  Exiting loop...\n")
            break
      #end while (number % factor) == 0

    # If the number is > 1 after exiting the loop,
    #   then the remaining value of the number must be the final prime factor.
    # It should be appended to the prime_factors list
    if number > 1:
        prime_factors.append(int(number))
        print("{} is a prime number".format(prime_factors[-1]))
    
# TASK 1: Sum all prime factors
    
    # Initialize or reset a variable to hold the sum of the prime factors
    sum_of_prime_factors = 0;
    # Iterate over the prime_factors list to obtain the sum
    for i in range(0, len(prime_factors)):
        sum_of_prime_factors += prime_factors[i]
    
    # Display the list of prime factors & their sum
    if len(prime_factors) > 1:
        displayFactors(HEADER_PRIME, prime_factors, sum_of_prime_factors)
    else:
        displayFactors(HEADER_BOTH, prime_factors, sum_of_prime_factors)
        continue
    
# TASK 2: Sum all unique prime factors
    
    # Initialize or reset a list to hold the sum of the unique prime factors
    unique_prime_factors = []
    
    # It's safe to seed the first value of the unique factors list
    #   because there will always be at least one prime factor
    unique_prime_factors.append(prime_factors[0])
    
    # Initialize or reset a variable to hold the sum of the unique prime factors
    sum_of_unique_prime_factors = 0
    
    
    for i in range(0, len(prime_factors)):
        if prime_factors[i] != unique_prime_factors[-1]:
            unique_prime_factors.append(prime_factors[i])
    
    for i in range(0, len(unique_prime_factors)):
        sum_of_unique_prime_factors += unique_prime_factors[i]
    
    # Display the unique prime factors & their sum
    displayFactors(HEADER_UNIQUE_PRIME, unique_prime_factors, sum_of_unique_prime_factors)

#15

So it's pretty messy, but if it helps someone find a better way to do it, fine by me.

I used recursion and a prime tuple I got off this guy to check for divisors and add those together. I think it should run pretty fast though the limitations are quite obvious. I also tried to be extra polite to all the functions.

def giveprimepls(n):
    prim=(2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83)#First so-and-so primes
    for x in range(len(prim)):
        result=n//prim[x]
        if n % prim[x] ==0 and result!=1:
            summs=giveprimepls(result)
            return summs+prim[x]+0 
            break
        elif x==len(prim)-1: #Main Setback here.
            return n    #Will not work properly for large primes
                #but solution is easy! just use bigger tuple duh doi
        else:
            continue

#User Interface below
daretocontinue=True                
num=int(raw_input("Welcome to PrimeSumFinder 2000GT \n\n Input number please!"))

if num<2:
    print "You can't do that!"
    daretocontinue=False

while daretocontinue:
    
    finalsum=giveprimepls(num)
    printed='\n The sum of prime factors of ' + str(num) +  ' is ' + str(finalsum) + '\n\n Type number to find another prime factor sum!\n Type letters to exit!'
    try:
        num=int(raw_input(printed))
        
    except ValueError:
        daretocontinue=False
        quit()

Edited a big oversight


#17

Oops! I realized that there are a couple of issues if I enter a number that results in floor(sqrt(number)) < 3. I'm working on updating to account for that now and will update the code above one it's resolved.

EDIT/UPDATE
All better!

I realized that the special case was not 1. The special cases are 1, 2, and 3, because these numbers are, themselves, prime. And it is mathematically impossible for them to have a prime factor that is > 1.

I also added a function to display results, both to be a bit DRY-er and to slightly increase readability of the code.


#18

Here is my answer, it's made of two functions, the first one receives a number and it returns a list with all the posible prime numbers. It only analizes odd numbers because even numbers can't be primes. The second function receives a number num, it calls the primes function and for every prime number, if it's a factor of num it will add it to value, which is the sum of all the prime numbers.

After I made this, i added a new parameter to the sum_primes function to allow calculate the sum of all of the unique primes.

def primes(number):
    primes_list = [2]
    max_num = number//2
    num = 3
    while True:
        add = True
        for elem in primes_list:
            if num % elem == 0:
                add = False
                break
        if add:
            primes_list.append(num)
        if num >= max_num:
            primes_list.append(number) # in case number is prime
            return primes_list
        num += 2
    return 

def sum_primes(num, unique=False):
    div = primes(num//2)
    value = 0

    while num > 1:
        d = div.pop(0)
        if unique:
            added = False
        while num % d == 0:
            num = num // d      
            if unique:
                if not added:
                    value += d
                    added = True
            else:
                value += d
            
    return value

num = int(input())
print(sum_primes(num))

#19

Hi, everyone! I built two functions: one sums all prime divisors and another - only unique ones. I've wrote some comments directly in program. Hope everything is clear and you'll like it :slight_smile: But I'll be thankful for any remarks or improovments.

# Python3, for natural numbers
def sum_prime_factors(n):
    if n in [2, 3]: return n # for case when n = 2 or 3, for 1 works correctly
    sum = 0
    for p in range(2, n//2+1): # every divisor is < or = half of number
        while n % p == 0: sum += p; n /= p # it's clear
    return sum

# same idea
def sum_unique_prime_factors(n):
    if n in [2, 3]: return n
    sum = 0
    for p in range(2, n//2+1):
        div = 0 # will contain current divisor if it is, else 0
        while n % p == 0: div = p; n /= p
        if div: sum += p # 0 has boolean value False, other numbers have True
    return sum

#20

def is_prime(n):
  """ (int) -> bool

  if the number is prime
    return True
  else 
    return False
    
  >>> is_prime(2)
  True
  >>> is_prime(3)
  True
  >>> is_prime(4)
  False
  >>> is_prime(5)
  True
  >>> is_prime(96)
  False
  >>> is_prime(97)
  True    
  """
  
  for i in range(n-1, 1, -1):
    if ((n%i) == 0):
      return False
  return True

def prime_factors_sum(n):
  """ (int) -> int
  
  Return the sum of the prime factors of n.
  
  >>> prime_factors_sum(24)
  9
  >>> prime_factors_sum(1092)
  27
  """
 
  current_prime = 2 
  a_factor_of_n = n 
  prime_factors_sum = 0
  
  while (a_factor_of_n != current_prime):
    if ((a_factor_of_n % current_prime) == 0): 
      prime_factors_sum += current_prime
      a_factor_of_n = (a_factor_of_n / current_prime)
    else: # not divisible by that prime
      # find the next prime
      current_prime += 1
      while ((not is_prime(current_prime)) and (current_prime < n)):
        current_prime += 1
        
  prime_factors_sum += current_prime
  
  return prime_factors_sum
   
if __name__ == '__main__':
  import doctest
  doctest.testmod()

#21

This python script calculates the sum of prime factors (>1)

for a positive integer 'n' >1

the underlying principle is Unique prime factorisation theorem

Created: 09-Apr-2017

def PrimefactorDecomposition(n):

#Let's first import an environment

from math import sqrt

# sub function to check if an Integer (nn) is prime

def isprime(nn):

	mm = int(sqrt(nn))
	# returns 0 or 1 if the number(>1) is composite or prime		

	if mm == 1:
		            y=1
		                                                
	else:
		            for i in range(2,mm):
		                    if nn%i == 0:                                        
		                            return False                                                                                    
		                            break
		



# the main loop to get sum of prime factors

if isprime(n)==	1:      # avoid the loop if we are luckily given a prime

	pf = [n] 	# prime factor decomposition
	upf = [n] 	# which is also the list of unique prime factors
	sum_upf	= [n] 	# the sum of unique prime factors
	pro_upf	= [n] 	# and the prouct of a single factor

else: 
	m = sqrt(n)	

	# avoid the loop if we are luckily given square of a prime
	if m == int(m) & isprime(m):
		pf = [m,m] 	        # prime factor decomposition
		upf = [m] 		# the list of unique prime factors
		sum_upf	= [m] 		# sum of unique prime factors
		pro_upf	= [m] 		# the prouct of a single factor

	else:	# the main loop

		m = int(m) 		# get the integer square root of number n
		pf = []			# initiate an empty array
	
		for i in range (2,m): 	# we have already covered numbers with sqrt<2

			if n % i == 0 & isprime(i):

                                    pf.append(i) 	# record the prime factor in the array
                                    n = n/i 	# reduction of n by dividing it with a prime factor
                                    i = i-1		# check for repeated divisibillity by the same factor

		# after the loop is over and we have pf [prime decomposition array]
		
		p = len(pf)	# length of pf array
		upf = []	# open an array of unique prime factors
		u = pf[0]

		upf.append(u)

		for j in range (1,p):	# p is >1, as primes have been covered above
			if pf[j] != pf[j-1]:
				upf.append(pf[j])       # update list of unique prime factors

		sum_upf	= [sum(upf)]	# update the sum of unique prime factors

		# another sub function to find product of an array

		def prod_array(array):
			a = len(array)
			p_a = 1
			for i in range (1,a):
				p_a = p_a*array(i)

			return p_a

		pro_upf	= [prod_array(upf)]


print 'Prime_factor_decomposition:'
print pf
print 'Unique_prime_factors:'
print upf
print 'Sum_of_Unique_prime_factors:'
print sum_upf
print 'Prom_of_Unique_prime_factors:'
print pro_upf