15
\$\begingroup\$

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 , so shortest answer in bytes wins.

\$\endgroup\$
9
  • \$\begingroup\$ Sandbox \$\endgroup\$
    – Stephen
    Aug 29, 2017 at 18:45
  • 7
    \$\begingroup\$ This is one of those challenges that I think is “too simple”. Almost every answer is gonna look like one of these: (a) a loop over the input, and Ye Olde Prime Factorization Code with a conditional append; (b) a chain of four built-ins. There just isn’t much room for creativity. Maybe the answers will prove me wrong, but I doubt it. There’s very little more to golf than prime factorization here, and that’s been done to death. \$\endgroup\$
    – Lynn
    Aug 29, 2017 at 19:02
  • 1
    \$\begingroup\$ @Lynn it's trivial for golfing langs, but non-trivial for nearly everything else. Not sure if that's grounds for triviality here :/ \$\endgroup\$
    – Stephen
    Aug 29, 2017 at 19:03
  • \$\begingroup\$ Can you tell me which are "the distinct prime factors" of 1? \$\endgroup\$
    – ZaMoC
    Aug 29, 2017 at 19:05
  • 1
    \$\begingroup\$ @DigitalTrauma Yes. Otherwise it would just be "output the set of all prime factors of the input" \$\endgroup\$
    – Stephen
    Aug 30, 2017 at 0:32

31 Answers 31

9
\$\begingroup\$

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!

\$\endgroup\$
2
  • 6
    \$\begingroup\$ Hah... f U. Love it. \$\endgroup\$ Aug 29, 2017 at 22:34
  • \$\begingroup\$ @MagicOctopusUrn Thanks :-) \$\endgroup\$
    – Mr. Xcoder
    Aug 29, 2017 at 22:35
5
\$\begingroup\$

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. 
\$\endgroup\$
4
  • 3
    \$\begingroup\$ Σ† can be . \$\endgroup\$
    – Zgarb
    Aug 29, 2017 at 19:44
  • \$\begingroup\$ @Zgarb Thanks a lot. As you can tell, it's my first Husk answer ever :) \$\endgroup\$
    – Mr. Xcoder
    Aug 29, 2017 at 19:44
  • \$\begingroup\$ It's nice to see new people using Husk. :) \$\endgroup\$
    – Zgarb
    Aug 29, 2017 at 19:53
  • 1
    \$\begingroup\$ @Zgarb It seems very nice (especially when it outgolfs Jelly :P) \$\endgroup\$
    – Mr. Xcoder
    Aug 29, 2017 at 19:53
5
\$\begingroup\$

Bash + GNU utilities, 37

  • 21 bytes saved thanks to @muru (wow!)
factor|tr \  \\n|awk '!/:/&&!a[$0]++'

Try it online.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ I think the nl|sort|... can be done using awk: awk '!a[$0]++' (print if not seen before; so order is never lost), saving 15 bytes. Then the sed command can be eliminated using a slightly longer awk one: factor|awk '!/:/&&!a[$0]++' RS='[ \n]+' (split records on spaces and newlines, skip records with :), saving another 4 bytes. \$\endgroup\$
    – muru
    Aug 30, 2017 at 5:07
  • 1
    \$\begingroup\$ I just realised I can save another two bytes on the previous comment by using tr: factor|tr \ \\n|awk '!/:/&&!a[$0]++' (that's two spaces after the first backslash) \$\endgroup\$
    – muru
    Aug 30, 2017 at 8:58
  • \$\begingroup\$ @muru awesome - thanks! (I wouldn't have been upset if you'd posted this as your own answer, that significantly out-golfed my original) \$\endgroup\$ Aug 30, 2017 at 16:53
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
0
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

CJam, 11 bytes

{:mfe__&1-}

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

Test Version

\$\endgroup\$
3
  • \$\begingroup\$ How would I differentiate output with multiple characters? At least for my (online) testing it outputs a string, not an array of ints. \$\endgroup\$
    – Stephen
    Aug 29, 2017 at 19:15
  • \$\begingroup\$ As a function, it's output datatype is an array of ints. CJam automatically prints ths stack, and it prints arrays w/o delimters. I don't know if that's good enough for your purposes. If you want delimeters add S* inside the close bracket. \$\endgroup\$
    – geokavel
    Aug 29, 2017 at 19:19
  • \$\begingroup\$ I believe stack-based langs can output by ToS anyway, so it's fine, I was just wondering. Thanks. \$\endgroup\$
    – Stephen
    Aug 29, 2017 at 19:20
3
\$\begingroup\$

Gaia, 4 bytes

ḍ¦_u

Try it online!


Explanation

ḍ¦      Prime factors of each.
  _     Flatten the list.
   u    Remove duplicate elements.
\$\endgroup\$
3
\$\begingroup\$

Jelly, 5 4 bytes

1 byte thanks to clap.

ÆfFQ

Try it online!

\$\endgroup\$
3
  • \$\begingroup\$ Not surprised . \$\endgroup\$
    – Leaky Nun
    Aug 29, 2017 at 18:58
  • \$\begingroup\$ Don't think you need to force vectorization on Æf, so you can probably drop a byte with ÆfFQ \$\endgroup\$
    – clapp
    Aug 29, 2017 at 19:30
  • 3
    \$\begingroup\$ @clap I'm an idiot... \$\endgroup\$
    – Leaky Nun
    Aug 29, 2017 at 19:40
2
\$\begingroup\$

Pyke, 4 bytes

MPs}

Try it here!


Explanation

MP       Prime factors of each.
  s      Flatten.
   }     Deduplicate.
\$\endgroup\$
2
\$\begingroup\$

Mathematica, 64 bytes

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

input

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

\$\endgroup\$
1
  • \$\begingroup\$ Select[#&@@@Gather[#&@@@Join@@FactorInteger@#],#>1&]& \$\endgroup\$
    – matrix42
    Aug 30, 2017 at 7:15
2
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

Brachylog, 6 bytes

ḋᵐoᵐcd

Try it online!

Explanation

ḋᵐ         Map prime decomposition
  oᵐ       Map order
    c      Concatenate
     d     Remove duplicates
\$\endgroup\$
5
  • \$\begingroup\$ Fais for [10,9,8,7,6,5,4,3,2,1]. It should be [2, 5, 3, 7], not [2, 3, 5, 7] \$\endgroup\$
    – Mr. Xcoder
    Aug 30, 2017 at 7:17
  • \$\begingroup\$ You can fix that for +1 byte: ḋᵐoᵐcd \$\endgroup\$
    – Mr. Xcoder
    Aug 30, 2017 at 7:19
  • \$\begingroup\$ @Mr.Xcoder Thanks, fixed. Pretty non-sensical requirement imo though. \$\endgroup\$
    – Fatalize
    Aug 30, 2017 at 7:27
  • \$\begingroup\$ It's not really non-sensical, as it is a tiny, tiny bit less trivial. I posted my own answer too, but I used reversed first instead of order. Not sure why the prime factors are generated in reverse order? \$\endgroup\$
    – Mr. Xcoder
    Aug 30, 2017 at 7:28
  • \$\begingroup\$ @Fatalize well - the challenge is not "sorted distinct prime factors of the list," it's "iterate through the list and append distinct prime factors." \$\endgroup\$
    – Stephen
    Aug 30, 2017 at 11:40
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

Japt, 6 bytes

mk c â

Test it


Explanation

Implicit input of array U. Map (m) over it, getting the factors (k) of each element. Flatten (c), get the unique elements (â) and implicitly output.

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
2
2
\$\begingroup\$

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.
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

Vyxal, 3 bytes

ǐfU

Try it Online!

ǐ   # prime factors
 f  # flattened
  U # uniquified
\$\endgroup\$
1
\$\begingroup\$

Pyke, 4 bytes

mPs}

Try it here!

mP   -   map(factorise, input)
  s  -  sum(^)
   } - uniquify(^)
\$\endgroup\$
3
  • \$\begingroup\$ Ouch, I ninja'd you badly - Good we have different approaches :) \$\endgroup\$
    – Mr. Xcoder
    Aug 29, 2017 at 19:13
  • \$\begingroup\$ :P One byte difference. I think it's allowed though or at least according to the last consensus I read \$\endgroup\$
    – Blue
    Aug 29, 2017 at 19:14
  • \$\begingroup\$ Yes, duplicate answers, even byte-to-byte are allowed \$\endgroup\$
    – Mr. Xcoder
    Aug 29, 2017 at 19:14
1
\$\begingroup\$

Octave, 61 bytes

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

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

J, 10 bytes

~.(#~*),q:

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

\$\endgroup\$
1
\$\begingroup\$

Actually, 5 bytes

♂y♂i╔

Try it online!

Explanation:

♂y♂i╔
♂y     prime factors of each element
  ♂i   flatten
    ╔  deduplicate (stable)
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$
6
  • \$\begingroup\$ This doesn't appear to be correct. The second test case should output [2, 5, 3, 7]. The order of the outputs matters. \$\endgroup\$
    – user45941
    Aug 30, 2017 at 9:48
  • \$\begingroup\$ sorted(set().union(*map(primefac,l))) \$\endgroup\$
    – Alex Hall
    Aug 30, 2017 at 11:22
  • \$\begingroup\$ The order of the outputs is important. Re-read the explanation, or look at other answers - I don't really know how else to explain it. \$\endgroup\$
    – Stephen
    Aug 30, 2017 at 11:37
  • \$\begingroup\$ @Stephen. Updated routine, with correct output. It took me a while until i noticed the differences in each line. Focus while reading helps a lot. \$\endgroup\$
    – Simon
    Aug 30, 2017 at 12:14
  • \$\begingroup\$ @Simon save three bytes by getting rid of spaces after parens - s.append(x) for -> s.append(x)for, primefac(i)) for -> primefac(i))for, []) if-> [])if \$\endgroup\$
    – Stephen
    Aug 30, 2017 at 12:35
1
\$\begingroup\$

APL (Dyalog Extended), 4 bytesSBCS

∪∘∊⍭

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ Fails for [10,9,8,7,6,5,4,3,2,1]. - The order matters: you should return [2, 5, 3, 7] instead of [2, 3, 5, 7]. \$\endgroup\$
    – Mr. Xcoder
    Sep 1, 2017 at 7:41
  • \$\begingroup\$ You can fix that for -1 byte though. Since K only makes harm here. \$\endgroup\$
    – Mr. Xcoder
    Sep 1, 2017 at 7:43
  • \$\begingroup\$ @Mr.Xcoder oh right yeah, didn't realise they were supposed to be in order of occurrence, not ascending order. Fixed \$\endgroup\$
    – Mayube
    Sep 1, 2017 at 8:11
1
\$\begingroup\$

Factor + math.primes.factors, 32 bytes

[ [ factors ] map-flat members ]

Try it online!

  • factors Get the prime factors of a number.
  • map-flat Apply a quotation to each member of a sequence, collecting the (non-scalar) results in a flat sequence of the same length.
  • members Remove duplicates.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.