[Challenge] Sum of Prime Factors

Hi all,

I was solving the intermediate problem - of finding the sum of each unique prime factor of a given number, n.
The answer in written in JavaScript and takes the approach of the the sieve of Eratosthenes - one of the methods for finding all prime numbers before n.
The original sieve starts with 2 and loops over all numbers until n. On the first loop we would cross out all of the numbers that can be divided by 2 without remainder (so, for 2 these will be 4, 6, etc). Then we would move to the next not-crossed number (3) and perform the loop once again. The next number to perform a loop on will be 5, as 4 is already crossed out.
In my case, in addition to crossing out the numbers I’m also storing the (primary) divisors of n - in other words, the loops that have ‘crossed out’ n. We need to do it only up until n/2, as the number above this will be a divisor of n only if it equals n.
Finally, if no divisors are stored, that means that n is a primary number - thus, we return n.

function getFactors(n) {
    var myPrimes = new Array(n+1),
        myFactors = [];
    for (var i = 2; i <= n / 2; i ++) {
        if (myPrimes[i] != 1) {
            for (var j = i + i; j <= n; j += i) {
                myPrimes[j] = 1;
                if (j == n) {
                    myFactors.push(i)
                }
            }
        }
    };
    return (myFactors.length == 0 ? n : myFactors.reduce( function(a, b) {return a + b} ) );
};
5 Likes

With massive thanks in particular to our resident expert @factoradic, here are our findings!

If we assume that there are n/log(n) primes less than n, then the sieve has O(n log log n) time complexity, and you need extra memory. In this case, it really makes sense to use a good implementation of trial division, or to use Pollard’s algorithm. Using a sieve is more often than not a bad idea, particularly when implemented less than perfectly.

Our challenge asked you to “try to write your function without using trial division,” which would leave @javawhiz18379 with the best answer. However, to allow for trial division (and we only asked you to try and avoid it), then @rublen would have the best answer here, with @codeplayer75939’s entry as a runner-up. @javawhiz18379 and @rublen - DM me with your Twitter usernames so we can give you mad props!


A few more notes:

@codeplayer75939: you had very good trial division, but using a global variable to store primes wasn’t the best route to take. However, great work for your first coding challenge and we liked your repli.it embed. :slight_smile:

@lancejz: very good trial division, but you print out prime factors, not their sum

@rjelavic very good trial division, but we didn’t like your use of recurrence

@christelleks good work, but your solution unnecessarily checks if the divisor is prime

For most of you, reworking your sieve or trial division would be ways to improve your entries.


Please read some more of Maciej’s commentary here and here to learn a bit more about solving this challenge.

Thank you everyone for participating! We were really impressed with what you came up with. Stay tuned for next week’s challenge!

3 Likes

Mind expanding stuff, to be sure; and, surely enjoyed getting to understand it (cough).

https://www.cs.colorado.edu/~srirams/courses/csci2824-spr14/pollardsRho.html

3 Likes

Hi, Daniel! Here’s my twitter Ruban @ DashaRuban77
Nice challenge, thanks :slight_smile:

I would like to elaborate a bit.

I really wasn’t expecting solutions using Eratosthenes sieve. It’s a great algorithm, but not suitable here. Let’s say that n = 104059 (prime number). Computer will use a lot of time and memory to find primes < 52300. Result of these computations will be used exactly 0 times. This is a huge loss! And this is why trial division algorithm outperforms this solution.


@codeplayer75939 Don’t repeat yourself, in imperative programming this rule is the main idea behind functions. Functions should (usually) encapsulate a complete part of the program logic. Your function uses a global list primes to store result of the findprimes function. This becomes problematic when we want to execute this function few times, before every function call we would need to assign to primes an empty list.

It’s a really small change, but makes your function much more usable:

def findprimes(n):
  primes=[]
  while n % 2 == 0:
    primes.append(2) 
    n=n/2
  i=3
  while i <= math.sqrt(n):
    while n % i == 0:
      primes.append(i)
      n=n/i
    i+=2
  if n>2:
    primes.append(n)
  return primes

@rjelavic I really like your solution! It’s awesome. But… when it comes to algorithmic problems we have to wisely choose techniques. Recursion is a great way to quickly prototype functions, it’s elegant, it’s simple to read and to write (right? :slight_smile:).

In imperative languages, there is a certain problem related to recursion - size limit of the call stack (stack overflow error). This makes your solution a bit less scalable. Python does not even optimise tail-recursion :frowning:

5 Likes

Hi guys, here is a javascript version with great efficiency:

function sumPrimes(num) {
  var n = 2,arr1=[], arr2=[], sqrt = 0;
  while(n <= num){
    sqrt = Math.floor(Math.sqrt(n));
    while(sqrt !== 1){
      if(n % sqrt === 0){
        arr1.push(sqrt);
      }
      sqrt--;
    }
    if(arr1.length === 0)
      arr2.push(n);
    arr1 = [];
    n++;
  }
  num = 0;
  arr2.forEach(function(a){
    num +=a;
  });
  return num;
}

sumPrimes(10);
1 Like

Hello :slight_smile:

The challenge is over, but I would like to give you a short feedback.


Your code calculates the sum of primes less than n. That is not the matter of this challenge. You were supposed to write a function that will return the sum of prime factors of n. In other words, the sum of primes that are factors of n.


with great efficiency

Unfortunately, this is not true. You are using trial division to find all the primes less than n. This is a great use case for a sieve (sieve of Eratosthenes or sieve of Atkin-Bernstein). Use of sieve would boost the efficiency of your function.

1 Like

Hi,

I’m a re-beginner in programming as I haven’t coded for many years. As a teenager I used to code in c64 assembler so I was mostly interested in a routine that completes quickly. Thanks to this challenge I have learned about the Big O Notation and tried to take advantage of it here.

This is a simple trial division algorithm very similar to the first one posted, but as the outer loop iterates by n that gets divided, I believe it runs at sublinear speed:

def listprimes(n):
    primes = []

    while (n % 2) == 0:           # n divides by 2
        primes.append(2)
        n = int(n / 2)
        if n == 1: return primes

    i = 3
    while n > 1:
        while (n % i) == 0:       # n divides by odd numbers
            primes.append(i)
            n = int(n / i)
        i += 2
        if i*i > n:
            if n > 1: primes.append(n)  # biggest prime factor
            break

    return primes


def sumuniqueprimes(n):
    j = 0
    for i in set(n): j += i
    return j

This code is faster than each of the other contributions I’ve tested.

The simplified version that doesn’t eliminate the even factors was faster only in some cases; the version that also eliminates factors divisible by 3 first was slower.

Here’s some support code I used to get input and measure runtime for anyone interested in optimizing their algorithms:

while True:
    try:
        n = int(input("Enter an integer >2: "))
    except ValueError: continue
    if n < 2: continue
    else: break

start = time.time()
factorlist = listprimes(n)
print(factorlist)
print("Sum of unique factors:", sumuniqueprimes(factorlist))
end = time.time()
print("Time elapsed:", end - start)

Thanks for the inspiration this challenge has been, perhaps I won’t be late to the next one =)

PS. rublen’s routine returns 0 when input is a prime.

1 Like

Hello :slight_smile:


I would like to start by answering this concern:

PS. rublen’s routine returns 0 when input is a prime.

That is true and I was aware of this. I have tested all the submissions, but because we didn’t get a perfect answer I decided to ignore simple coding mistakes and focus on used methods. To fix @rublen code you just need to modify the return statement:

return n if sum == 0 else sum

My methods are open for discussion. I would love to hear what others think :slight_smile:


Your solution is really good. It’s almost perfect if we limit ourselves to trial division. I would change only one thing, I would calculate sum on the fly, instead of creating a list of prime factors. This change would result in faster execution and less memory use.

I agree that it might be handy to have a function that calculates the list of prime factors, but in algorithmic problems, you have to focus on the specific task.

Very good job! I hope that you will take part in the next challenge :slight_smile:

2 Likes

Hi guys! Yeah, I’ve missed the case when n is prime. Shame of me. Here’s my improving:

def sum_prime_factors(n):
    if n == 1: return 0
    sum = 0
    for p in range(2, n//2+1):
        while n % p == 0: sum += p; n /= p
    return sum if sum else n

def sum_unique_prime_factors(n):
    if n == 1: return 0
    sum = 0
    for p in range(2, n//2+1):
        div = 0
        while n % p == 0: div = p; n /= p
        if div: sum += p
    return sum if sum else n

b-twin I liked your support code and I tried it, of course your code is faster but I decided to sacrifice efficiency for the sake of prettiness this time :slight_smile:

1 Like

Hi all, another little piece of java, not for challenge, just for the fun of coding and remembering such basic knowledge as factorization/prime factorization
I have

  • 2 public functions: one with sum of all prime factors, second with sum of only unique prime factors.
  • 2 private functions: one checks if a int number is prime other one computes recursively the sum for the same prime factor
    Also, I’m considering first prime number 2.
    Java program:
package ro.khrypt.codekata.codeacademy;

import org.apache.log4j.Logger;

public class SumOfPrimeFactorsOfGivenNumber {

    private static final Logger log = Logger.getLogger(SumOfPrimeFactorsOfGivenNumber.class);

    public int sumOfUniquePrimeFactors(int n) {
        int sum = 0;

        if (n > 1) {
            if (isPrime(n)) {
                return n;
            }
            for (int i = 2; i < n / 2 + 1; i++) {
                if (isPrime(i)) {
                    if (n % i == 0) {
                        sum += i;
                    }
                }
            }
        }
        return sum;
    }

    public int sumOfPrimeFactors(int n) {
        int sum = 0;

        if (n > 1) {
            if (isPrime(n)) {
                return n;
            }
            for (int i = 2; i < n / 2 + 1; i++) {
                if (isPrime(i)) {
                    sum = localPrimesSum(n, i, sum);
                }
            }
        }
        return sum;
    }

    private int localPrimesSum(int n, int prime, int sum) {
        if (n > 1) {
            if (n % prime == 0) {
                sum = localPrimesSum(n / prime, prime, sum + prime);
            }
        }
        return sum;
    }

    private boolean isPrime(int n) {
        if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11 || n == 13 || n == 17 || n == 19) {
            return true;
        }
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                return false;
            }
        }
        return true;
    }

}

Java test class:

package ro.khrypt.codekata.codeacademy;

import org.apache.log4j.Logger;
import org.junit.Assert;
import org.junit.Test;

public class SumOfPrimeFactorsOfGivenNumberTest {

    private static final Logger log = Logger.getLogger(SumOfPrimeFactorsOfGivenNumberTest.class);

    @Test
    public void testSumOfPrimeFactors() {
        SumOfPrimeFactorsOfGivenNumber sn = new SumOfPrimeFactorsOfGivenNumber();
        
        Assert.assertEquals(2, sn.sumOfPrimeFactors(2));
        Assert.assertEquals(3, sn.sumOfPrimeFactors(3));
        Assert.assertEquals(5, sn.sumOfPrimeFactors(5));
        Assert.assertEquals(7, sn.sumOfPrimeFactors(7));
        Assert.assertEquals(4, sn.sumOfPrimeFactors(4));
        Assert.assertEquals(5, sn.sumOfPrimeFactors(6));
        Assert.assertEquals(6, sn.sumOfPrimeFactors(9));
        Assert.assertEquals(11, sn.sumOfPrimeFactors(11));
        Assert.assertEquals(7, sn.sumOfPrimeFactors(12));
        Assert.assertEquals(13, sn.sumOfPrimeFactors(13));
        Assert.assertEquals(9, sn.sumOfPrimeFactors(14));
        Assert.assertEquals(8, sn.sumOfPrimeFactors(15));
        Assert.assertEquals(8, sn.sumOfPrimeFactors(16));
        Assert.assertEquals(17, sn.sumOfPrimeFactors(17));
        Assert.assertEquals(8, sn.sumOfPrimeFactors(18));
        Assert.assertEquals(19, sn.sumOfPrimeFactors(19));
        Assert.assertEquals(13, sn.sumOfPrimeFactors(22));
        Assert.assertEquals(10, sn.sumOfPrimeFactors(36));
        Assert.assertEquals(28, sn.sumOfPrimeFactors(456));
        Assert.assertEquals(140, sn.sumOfPrimeFactors(2620));
       
    }
    
    @Test
    public void testSumOfUniquePrimeFactors() {
        SumOfPrimeFactorsOfGivenNumber sn = new SumOfPrimeFactorsOfGivenNumber();

        Assert.assertEquals(2, sn.sumOfUniquePrimeFactors(2));
        Assert.assertEquals(3, sn.sumOfUniquePrimeFactors(3));
        Assert.assertEquals(5, sn.sumOfUniquePrimeFactors(5));
        Assert.assertEquals(7, sn.sumOfUniquePrimeFactors(7));
        Assert.assertEquals(2, sn.sumOfUniquePrimeFactors(4));
        Assert.assertEquals(5, sn.sumOfUniquePrimeFactors(6));
        Assert.assertEquals(3, sn.sumOfUniquePrimeFactors(9));
        Assert.assertEquals(11, sn.sumOfUniquePrimeFactors(11));
        Assert.assertEquals(5, sn.sumOfUniquePrimeFactors(12));
        Assert.assertEquals(13, sn.sumOfUniquePrimeFactors(13));
        Assert.assertEquals(9, sn.sumOfUniquePrimeFactors(14));
        Assert.assertEquals(8, sn.sumOfUniquePrimeFactors(15));
        Assert.assertEquals(2, sn.sumOfUniquePrimeFactors(16));
        Assert.assertEquals(17, sn.sumOfUniquePrimeFactors(17));
        Assert.assertEquals(5, sn.sumOfUniquePrimeFactors(18));
        Assert.assertEquals(19, sn.sumOfUniquePrimeFactors(19));
        Assert.assertEquals(13, sn.sumOfUniquePrimeFactors(22));
        Assert.assertEquals(5, sn.sumOfUniquePrimeFactors(36));
        Assert.assertEquals(24, sn.sumOfUniquePrimeFactors(456));
        Assert.assertEquals(138, sn.sumOfUniquePrimeFactors(2620));

    }

}

In the end, shame on me, I don’t have substantial knowledge and understanding for On …
Have a nice day

1 Like

Maybe a little late to the game, but used brute force method in C++ to find prime factors. Prompts user for int and calls function with nested for loops to first find all factors, then determines if prime. Adds primes together and prints result. Also counts for unique primes and prints unique prime if there is only 1 prime factor of the original number. Otherwise there are no unique primes. I don’t know if I understood the definition of intermediate question. If it’s unique, there is just 1 so you don’t need to add anything. Anyways, curious to read the sub-linear time solutions…

#include <iostream>

int n;

int prime_sum(int a){
    int sum {0};
    int cnt {0};
    int run_sum {0};
    for (int i=1; i<= a; i++){ //first for loop finds all factors
        if (a%i == 0){
            sum = 0;
            for (int j=1; j <= i; j++){ //second for loop finds prime factors
                if (i%j == 0)
                    sum += 1;
            }
            if (sum == 2){
                    run_sum = run_sum + i;
                    cnt += 1;
            }
        }
    }
    std::cout << "sum of all prime factors:" << run_sum << "\n"; //prints running sum of all prime factors
    if (cnt == 1 )
        std::cout << "sum of unique primes:" << run_sum << "\n"; //prints sum of unique primes only if there is one prime factor of int a
    else
        std::cout << "No unique primes." << "\n";
}
int main () {
    std::cout << "Enter integer:" << "\n";
    std::cin >> n;
    prime_sum(n);
    return 0;
}
1 Like

Here’s the proper summing function for the sake of the archives:

def sumprimes(n):
    upfsum = 0

    while (n % 2) == 0:           # n divides by 2
        n = int(n / 2)
        if n == 1: return 2
        upfsum = 2

    i = 3
    lastupf = 2
    while n > 1:
        while (n % i) == 0:       # n divides by odd numbers
            if i != lastupf:
                lastupf = i
                upfsum += i
            n = int(n / i)
        i += 2
        if i*i > n:
            if n > 1: upfsum += n  # biggest prime factor
            break

    return upfsum

The speed improvement is negligible in this case, but of course I get the point. Thanks for the feedback!

My solution to the intermediate level of this Challenge…Need some help with the advanced level(sublinear time). Please reply if there are any answers to that part of the question…

Solution in PHP

function prime($input){
	$n = $input;
	$prime_factors = [];
	for($i=2; $i < $n; $i++){
		$flag = 0;
		for($j=2; $j<$i; $j++){
			if($i % $j == 0){
				$flag = 1;
			}
		}
		if($flag == 0){
			if($n % $i == 0){
				array_push($prime_factors, $i);
			}
		}
	}
	print_r($prime_factors);
}
prime($argv[1]);

basic difficulty using python

def sum_of_all_prime_factors(n):
      Sum=[] #declaring a list without any elements in it
      a=[2,3]# list with 2,3 as elements
      i=2
      count=0     
      while x in a:
            if n%x==0:
                 Sum.append(x)
                 n=n/x
       while i<n:
            if n%i==0:
                  count=1
                  break 
       if count == 1:
              return sum_of_all_prime_factors(n)
       else:
               Sum.append(n)
       for s in Sum:
             y+=s
       return "sum is:"+y

That’s really cognitive information to know about such a indomitable and concrete stuffs. I stolidly respect that effort and hope to keep the good work as same as always. Thank you for being so workaholic, it has server us the way we want. Indeed , grateful to you.

1 Like