Codewars task that Iliked

00_task.md

my solution (in my test case { 12657445, 89745368, 1235437 }) is about 1000x faster than most popular solution on codewars.

Sum by Factors https://www.codewars.com/kata/54d496788776e49e6b00052f

Given an array of positive or negative integers

I= [i1,..,in]

you have to produce a sorted array P of the form

[ [p, sum of all ij of I for which p is a prime factor (p positive) of ij] ...]

P will be sorted by increasing order of the prime numbers. The final result has to be given as a string in Java, C#, C, C++ and as an array of arrays in other languages.

Example:

I = {12, 15}; // result = "(2 12)(3 27)(5 15)"
[2, 3, 5] is the list of all prime factors of the elements of I, hence the result.

Notes:

It can happen that a sum is 0 if some numbers are negative!
Example: I = [15, 30, -45] 5 divides 15, 30 and (-45) so 5 appears in the result, the sum of the numbers for which 5 is a factor is 0 so we have [5, 0] in the result amongst others.

solution.cs

using System;
using System.Linq;
using System.Collections.Generic;

public class SumOfDivided {
  
  public static HashSet<int> cache;
  
  public static string sumOfDivided(int[] lst)
  {
      var d = new Dictionary<int, long>();
      cache = new HashSet<int>();

      foreach (var n in lst)
      {
          var primeFactors = FindPrimeFactors(Math.Abs(n));
          foreach (var f in primeFactors)
          {
              if (!d.TryAdd(f, n)) d[f] += n;
          }
      }

      var a = d.Keys.ToArray();
      Array.Sort(a);
      var s = "";

      foreach (var f in a)
      {
          s+=String.Format("({0} {1})", f, d[f]);
      }

      return s;
  }


  private static HashSet<int> FindPrimeFactors(int n)
  {
      var r = new HashSet<int>();

      for (int i=(int)Math.Sqrt(n); i > 1; i--)
      {
          if (n%i==0)
          {
              if (cache.Contains(i)) r.Add(i);
              else r.UnionWith(FindPrimeFactors(i));

              int f = n / i;
              if (cache.Contains(f)) r.Add(f);
              else r.UnionWith(FindPrimeFactors(f));
          }
      }

      if (r.Count == 0) r.Add(n);
      cache.UnionWith(r);
      return r;
  }
       
}