Array Factorization

Question

Given an array of positive integers, output a stable array of the distinct prime factors of these integers. In other words, for each integer in the input in order, get its prime factors, sort them, and append any primes not already in the output to the output.

Test Cases

[1,2,3,4,5,6,7,8,9,10] -> [2,3,5,7]
[10,9,8,7,6,5,4,3,2,1] -> [2,5,3,7]
[100,99,98,1,2,3,4,5] -> [2,5,3,11,7]
[541,60,19,17,22] -> [541,2,3,5,19,17,11]
[1,1,2,3,5,8,13,21,34,45] -> [2,3,5,13,7,17]
[6,7,6,7,6,7,6,5] -> [2,3,7,5]
[1] -> []
[8] -> [2]
[] -> []

Output can be as an array or list of integers or strings, delimited output, or any other standard means of outputting an ordered list of numbers.

This is code-golf, so shortest answer in bytes wins.

Answer 1

05AB1E, 3 bytes

Outputs as a list of Strings.

f˜Ù

Try it online!

2sable, 3 bytes

Yes, this also works in 2sable. Also returns a list of Strings.

f˜Ù

Try it online!

Answer 2

Husk, 3 bytes

1 byte saved thanks to @Zgarb.

uṁp

Try it online!

---

Explanation

uṁp    Full program.

  p    Prime factors of each.
 ṁ     Map function over list and concatentate the result.
u      Unique. 

Answer 3

Bash + GNU utilities, 37

• 21 bytes saved thanks to @muru (wow!)

factor|tr \  \\n|awk '!/:/&&!a[$0]++'

Try it online.

Answer 4

MATL, 6 bytes

"@Yfvu

Try it online!

Explanation:

"      % Loop over input
 @     % Push the array element
  Yf   % Prime factors
    v  % Concatenate entire stack vertically (does nothing the first iteration)
     u % Stably get distinct (unique, in MATLAB terminology) elements. Does so every loop but this is code golf, not fastest code.

Interesting MATL tidbits: generally, all functions apply to vectors (arrays) just as easily. But in this case, the number of factors is variable for each input, and Matlab and by extension MATL generally only deal in square matrices, so I had to use a for loop ".

Furthermore, MATL has two main concatenation operators: h and v, horizontal and vertical concatenation. Their behaviour differs significantly: v concatenates the entire stack, even if it has only one element like in our first iteration. h takes exactly two elements and will fail if only one is present, making it unsuitable for this application.

Answer 5

Brachylog, 6 bytes

ḋᵐ↔ᵐcd

Try it online!

Brachylog, 6 bytes

ḋᵐoᵐcd

Try it online!

---

Explanation

ḋᵐ       Map  with prime decomposition (which returns the factors in reverse order).
  ↔ᵐ     Reverse each (or oᵐ - order each).
    c    Concatenate (flatten).
     d   Deduplicate.

Answer 6

Pyth, 5 4 bytes

{smP

Try it here! or Verify all test cases.

Alternative: {sPM

---

Explanation

{smP      Full program with implicit input (Q).
  m       Map over the input.
   P      Prime factors.
 s        Flatten.
{         Deduplicate.

Answer 7

PowerShell, 102 bytes

param($x)$a=@();$x|%{$a+=(2..($z=$_)|?{!($z%$_)-and'1'*$_-match'^(?!(..+)\1+$)..'}|sort)};$a|select -u

Try it online!

(Borrows factorization idea from TessellatingHeckler's answer over on "Get thee behind me Satan-Prime!")

Takes input as a literal array $x. Creates a new empty array $a. Loops over $x. Each iteration we loop from 2 up to the current number, checking whether that is a factor -and is prime, then |sort the output of that, and append it to $a. When we're done going through $x, we then output $a but |select only the -unique numbers thereof. This exploits the fact that the uniqueify goes left-to-right, keeping the first occurrence, which matches the problem description. Those numbers are left on the pipeline and output is implicit.

Answer 8

CJam, 11 bytes

{:mfe__&1-}

Function that takes array of ints and outputs array of ints.

Test Version

Answer 9

Gaia, 4 bytes

ḍ¦_u

Try it online!

---

Explanation

ḍ¦      Prime factors of each.
  _     Flatten the list.
   u    Remove duplicate elements.

Answer 10

Jelly, 5 4 bytes

1 byte thanks to clap.

ÆfFQ

Try it online!

Answer 11

Pyke, 4 bytes

MPs}

Try it here!

---

Explanation

MP       Prime factors of each.
  s      Flatten.
   }     Deduplicate.

Answer 12

Mathematica, 64 bytes

Select[DeleteDuplicates[First/@FactorInteger@#~Flatten~1],#>1&]&

input

[{100, 99, 98, 1, 2, 3, 4, 5}]

Answer 13

Haskell, 77 bytes

import Data.List
x!y|y>x=[]|x`mod`y<1=y:(x`div`y)!y|1<2=x!(y+1)
nub.((!2)=<<)

Explanation:

• the x!y operator returns a list of all prime factors of x that are greater than or equal to y
• the (!2) function returns a list of all prime factors of its argument
• the function on the last line implements the required functionality

Try it online.

Answer 14

Brachylog, 6 bytes

ḋᵐoᵐcd

Try it online!

Explanation

ḋᵐ         Map prime decomposition
  oᵐ       Map order
    c      Concatenate
     d     Remove duplicates

Answer 15

Ohm v2, 3 bytes

Yet another 3-byter (thanks to languages with auto-vectorization).

m{U

Try it online!

---

Explanation

m      Prime factors. Auto-vectorizes over the input.
 {     Flatten.
  U    Uniquify.

Answer 16

Python 3, 128 125 116 bytes

This is a pure Python solution. No packages. Thanks to Halvard for saving 9 bytes.

def f(l):y=[k for i in l for k in range(2,i+1)if i%k<1*all(k%x for x in range(2,k))];print(sorted({*y},key=y.index))

Try it online!

Python 2, 133 127 126 bytes

def f(l):y=sum([[k for k in range(2,i+1)if i%k<1*all(k%x for x in range(2,k))]for i in l],[]);print sorted(set(y),key=y.index)

Try it online!

Python 2, 142 138 134 bytes

l=input();r=[]
for i in sum([[k for k in range(2,i+1)if i%k<1*all(k%x for x in range(2,k))]for i in l],[]):r+=[i]*(i not in r)
print r

Try it online!

Very surprised there was no Python answer yet. Working on golfing.

Answer 17

Deorst, 16 bytes

EDkE]l1FeFPkEQE_

Try it online!

Done with help from @cairdcoinheringaahing in the Deorst chatroom (note that the solutions are different).

---

Explanation

EDkE]l1FeFPkEQE_   Full program.

ED                 Push the list of divisors of each element.
  k                Prevent the stack from reordering.
   E]              Flatten the stack.
     l1Fe          Remove 1s from the stack (because caird rushed and made 1 prime!) - Should be removed in future language releases.
         FP        Keep the primes.
           k       Prevent the stack from reordering.
            EQ     Deduplicate.
              E_   Output the result.

Answer 18

Deorst, 16 bytes

EDkE]EQFPkl1FeE_

Try it online!

Done with help from @Mr.Xcoder. This is way too long for a pseudogolfing language.

How it works

EDkE]EQFPkl1FeE_ - Full program, implicit input: [1,2,3,4,5]

ED               - Get divisors. Vectorizes. STACK = [[1], [1,2], [1,3], [1,2,4], [1,5]]
  k              - Turn off sorting for the next command
   E]            - Flatten the stack. STACK = [1, 1, 2, 1, 3, 1, 2, 4, 1, 5]
     EQ          - Deduplicate stack in place. STACK = [1, 2, 3, 4, 5]
       FP        - Filter by primality 1 is considered prime. STACK = [1, 2, 3, 5]
         k       - Turn off sorting for the next command
          l1     - Push 1. STACK = [1, 2, 3, 5, 1]
            Fe   - Filter elements that are equal to the last element. STACK = [2, 3, 5]
              E_ - Output the whole stack

Answer 19

Vyxal, 3 bytes

ǐfU

Try it Online!

ǐ   # prime factors
 f  # flattened
  U # uniquified

Answer 20

Ruby -rprime, 50 bytes

->x,*r{x.map{_1.prime_division.map{|b,|r|=[b]}};r}

Attempt This Online!

Answer 21

Japt, 6 4 bytes

ck â

Try it

ck â     :Implicit input of array
c        :Flat map
 k       :  Prime factors
   â     :Deduplicate

Answer 22

Pyke, 4 bytes

mPs}

Try it here!

mP   -   map(factorise, input)
  s  -  sum(^)
   } - uniquify(^)

Answer 23

Octave, 61 bytes

a=input('');b=[];for c=a(a>1)b=[b setdiff(factor(c),b)];end;b

Try it online!

Answer 24

MY, 17 bytes

⎕Ḋḟ’⊢f(‘53ǵ'ƒf(ū←

Try it online!

How?

• ⎕ evaluated input
• Ḋ divisors (vectorizes/vecifies)
• ḟ flatten
• ’⊢f(‘ decrement, filter, increment (removes 1)
• 53ǵ' the string 'P' in MY's codepage, which is primality testing. Sadly 0x35=53 is the 16th prime number, and there's not a command for pushing 16 to the stack >_< .
• ƒ as a function
• f( filter by that
• ū uniquify
• ← output

Answer 25

C++, 118 bytes

[](auto n){decltype(n)r;for(int m:n)for(int i=1,j;i++<m;){j=m%i;for(int x:r)j|=!(i%x);if(!j)r.push_back(i);}return r;}

Needs to be passed the input in a std::vector<int>, returns another std::vector<int> for output.

Answer 26

J, 10 bytes

~.(#~*),q:

I'm sure some clever J-er could make this shorter.

Answer 27

Actually, 5 bytes

♂y♂i╔

Try it online!

Explanation:

♂y♂i╔
♂y     prime factors of each element
  ♂i   flatten
    ╔  deduplicate (stable)

Answer 28

Python 2, 88 119 103 bytes

Here we go. With the correct sorting.

def f(l,s=[]):[s.append(x) for x in sum([list(primefac(i)) for i in l],[]) if x not in s];print s
from primefac import*

Apperently I can't get it to work on TIO, because the package is not supported. It does run on my machine tho. Here are my Test outputs:

f([1,2,3,4,5,6,7,8,9,10],[])     #[2, 3, 5, 7]
f([10,9,8,7,6,5,4,3,2,1],[])     #[2, 5, 3, 7]
f([100,99,98,1,2,3,4,5],[])      #[2, 5, 3, 11, 7]
f([541,60,19,17,22],[])          #[541, 2, 3, 5, 19, 17, 11]
f([1,1,2,3,5,8,13,21,34,45],[])  #[2, 3, 5, 13, 7, 17]
f([6,7,6,7,6,7,6,5],[])          #[2, 3, 7, 5]
f([1],[])                        #[]
f([8],[])                        #[2]
f([],[])                         #[]

Somehow I was not able to make the function as a lambda-function. Whenever i try to return the list comprehention, it returns [None, None, ...]. If i am just overlooking something, could someone point that mistake out? Thanks for the feedback!

---

Edit:

Using Mr. Xcoders sorting algorithm I could cut down the code by 16 bytes. Thank you for that part.

from primefac import*
def f(l):a=sum([list(primefac(i))for i in l],[]);print sorted(set(a),key=a.index)

Answer 29

APL (Dyalog Extended), 4 bytes^SBCS

∪∘∊⍭

Try it online!

Answer 30

Braingolf, 7 bytes

&(p)u=;

Try it online!

Oh look, it's basically a chain of 4 built-ins

Explanation

&(p)u=;  Implicit input from commandline args
 (.)     Sandbox loop, sandboxes each item in a separate stack and runs the
         code within the loop.
&        Append the entire sandboxed stack when loop ends, rather than only the
         top of stack after each iteration
  p      Prime factors
    u    Unique
     =   Print stack
      ;  Suppress implicit output

Braingolf v2, 5 bytes

&pu=;

Try it online!

Braingolf's v2 interpreter doesn't have the "sandbox loop" (.) implemented yet, however due to more consistent modifier behavior, it's not needed for this challenge, as the greedy & modifier works directly on the prime factors p instruction, causing it to factorize every item on the stack.