12
\$\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\$
  • \$\begingroup\$ Sandbox \$\endgroup\$ – Stephen Aug 29 '17 at 18:45
  • 5
    \$\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 '17 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 '17 at 19:03
  • \$\begingroup\$ Can you tell me which are "the distinct prime factors" of 1? \$\endgroup\$ – J42161217 Aug 29 '17 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 '17 at 0:32

28 Answers 28

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\$
  • 6
    \$\begingroup\$ Hah... f U. Love it. \$\endgroup\$ – Magic Octopus Urn Aug 29 '17 at 22:34
  • \$\begingroup\$ @MagicOctopusUrn Thanks :-) \$\endgroup\$ – Mr. Xcoder Aug 29 '17 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\$
  • 3
    \$\begingroup\$ Σ† can be . \$\endgroup\$ – Zgarb Aug 29 '17 at 19:44
  • \$\begingroup\$ @Zgarb Thanks a lot. As you can tell, it's my first Husk answer ever :) \$\endgroup\$ – Mr. Xcoder Aug 29 '17 at 19:44
  • \$\begingroup\$ It's nice to see new people using Husk. :) \$\endgroup\$ – Zgarb Aug 29 '17 at 19:53
  • 1
    \$\begingroup\$ @Zgarb It seems very nice (especially when it outgolfs Jelly :P) \$\endgroup\$ – Mr. Xcoder Aug 29 '17 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\$
  • 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 '17 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 '17 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\$ – Digital Trauma Aug 30 '17 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\$
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\$
  • \$\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 '17 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 '17 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 '17 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\$
  • \$\begingroup\$ Not surprised . \$\endgroup\$ – Leaky Nun Aug 29 '17 at 18:58
  • \$\begingroup\$ Don't think you need to force vectorization on Æf, so you can probably drop a byte with ÆfFQ \$\endgroup\$ – clap Aug 29 '17 at 19:30
  • 3
    \$\begingroup\$ @clap I'm an idiot... \$\endgroup\$ – Leaky Nun Aug 29 '17 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\$
  • \$\begingroup\$ Select[#&@@@Gather[#&@@@Join@@FactorInteger@#],#>1&]& \$\endgroup\$ – mathe Aug 30 '17 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\$
  • \$\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 '17 at 7:17
  • \$\begingroup\$ You can fix that for +1 byte: ḋᵐoᵐcd \$\endgroup\$ – Mr. Xcoder Aug 30 '17 at 7:19
  • \$\begingroup\$ @Mr.Xcoder Thanks, fixed. Pretty non-sensical requirement imo though. \$\endgroup\$ – Fatalize Aug 30 '17 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 '17 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 '17 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
\$\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\$
1
\$\begingroup\$

Pyke, 4 bytes

mPs}

Try it here!

mP   -   map(factorise, input)
  s  -  sum(^)
   } - uniquify(^)
\$\endgroup\$
  • \$\begingroup\$ Ouch, I ninja'd you badly - Good we have different approaches :) \$\endgroup\$ – Mr. Xcoder Aug 29 '17 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 '17 at 19:14
  • \$\begingroup\$ Yes, duplicate answers, even byte-to-byte are allowed \$\endgroup\$ – Mr. Xcoder Aug 29 '17 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\$
  • \$\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\$ – Mego Aug 30 '17 at 9:48
  • \$\begingroup\$ sorted(set().union(*map(primefac,l))) \$\endgroup\$ – Alex Hall Aug 30 '17 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 '17 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 '17 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 '17 at 12:35
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
\$\endgroup\$
  • \$\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 '17 at 7:41
  • \$\begingroup\$ You can fix that for -1 byte though. Since K only makes harm here. \$\endgroup\$ – Mr. Xcoder Sep 1 '17 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\$ – Skidsdev Sep 1 '17 at 8:11
1
\$\begingroup\$

APL (Dyalog Extended), 4 bytesSBCS

∪∘∊⍭

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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