12
\$\begingroup\$

I saw another prime challenge coming by in PPCG, and I do love me some primes. Then I misread the introductory text, and wondered what the creative brains here had come up with.

It turns out the question posed was trivial, but I wonder if the same is true of the question I (mis)read:

\$6\$ can be represented by \$2^1\times3^1\$, and \$50\$ can be represented by \$2^1\times5^2\$.

Your task:

Write a program or function to determine how many distinct primes there are in this representation of a number.

Input:

An integer \$n\$ such that \$1 < n < 10^{12}\$, taken by any normal method.

Output:

The number of distinct primes that are required to represent the unique prime factors of \$n\$.

Test cases:

Input      Factorisation      Unique primes in factorisation representation
24         2^3*3^1            2 (2, 3)
126        2^1*3^2*7^1        3 (2, 3, 7)
8          2^3                2 (2, 3)
64         2^6                1 (2) (6 doesn't get factorised further)
72         2^3*3^2            2 (2, 3)
8640       2^6*3^3*5^1        3 (2, 3, 5)
317011968  2^11*3^5*7^2*13^1  6 (2, 3, 5, 7, 11, 13)
27         3^3                1 (3)

This is not an OEIS sequence.

Scoring:

This is , lowest score in bytes wins!

Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ What is the expected result for 64? Is it 2 (2,3) (as 6 can be represented as 2*3) or 1 (2) (ignore the 6)? \$\endgroup\$
    – Emigna
    Commented Oct 9, 2017 at 12:38
  • \$\begingroup\$ for 64 the expected result is 1 (2). I like the idea of doing it recursively, but that's not the way I read the original question. I thought 8640 was a suitable test case, but should have been more explicit - thanks. \$\endgroup\$
    – pbeentje
    Commented Oct 9, 2017 at 12:55
  • \$\begingroup\$ You claim this is not an OEIS sequence. Is it not A001221, the values of the (small) omega function? \$\endgroup\$
    – Gray Taylor
    Commented Oct 10, 2017 at 9:39
  • \$\begingroup\$ A001221 is similar, but starts to diverge at terms 8 and 9 (here 2, A001221 1) because of the inclusion of the exponent as prime in this exercise. \$\endgroup\$
    – pbeentje
    Commented Oct 10, 2017 at 10:59
  • \$\begingroup\$ Ah, I see. Write down the prime factorisation, then see how many different primes I wrote (regardless of the role they played). I wonder what happens if you go a step further and factorise the exponent... \$\endgroup\$
    – Gray Taylor
    Commented Oct 10, 2017 at 13:45

24 Answers 24

Reset to default
5
\$\begingroup\$

Jelly,  9  7 bytes

ÆFFQÆPS

Try it online! or Check out the test Suite.

How?

ÆFFQÆPS   ~ Full program.

ÆF        ~ Prime factorization as [prime, exponent] pairs.
  F       ~ Flatten.
   Q      ~ Deduplicate.
    ÆP    ~ For each, check if it is prime. 1 if True, 0 if False.
      S   ~ Sum.
Improve this answer
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 39 bytes

Count[Union@@FactorInteger@#,_?PrimeQ]&

Try it online!

thanks to Martin Ender (-11 bytes)

Improve this answer
\$\endgroup\$
3
  • \$\begingroup\$ Cases turns out to be shorter than Select (-4 bytes): Tr[1^Union@Cases[FactorInteger@#,_?PrimeQ,2]]& (passes all test cases on a fresh kernel) \$\endgroup\$
    – JungHwan Min
    Commented Oct 9, 2017 at 13:53
  • \$\begingroup\$ How about Count[Union@@FactorInteger@#,_?PrimeQ]&? (Haven't checked all test cases.) \$\endgroup\$
    – Martin Ender
    Commented Oct 9, 2017 at 17:36
  • \$\begingroup\$ @MartinEnder seems like it should work. Passes all test cases too. \$\endgroup\$
    – JungHwan Min
    Commented Oct 10, 2017 at 0:30
5
\$\begingroup\$

05AB1E, 9 7 bytes

Saved 2 bytes thanks to Kevin Cruijssen

ÓsfìÙpO

Try it online!

Explanation

Ó        # push the prime factor exponents of the input
 sfì     # prepend the prime factors of the input
    Ù    # remove duplicates
     p   # check each if it is prime
      O  # sum
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ -1 byte by using €pO after merging the prime factors and exponents: ÓsfìÙ€pO \$\endgroup\$
    – Kevin Cruijssen
    Commented May 6, 2019 at 10:59
  • \$\begingroup\$ @KevinCruijssen: Thanks! Actually saves 2 since € isn't needed. \$\endgroup\$
    – Emigna
    Commented May 6, 2019 at 11:27
  • \$\begingroup\$ Ah, of course.. Wow, not sure how I missed that, haha xD \$\endgroup\$
    – Kevin Cruijssen
    Commented May 6, 2019 at 11:28
5
+50
\$\begingroup\$

R + numbers, 80 78 bytes

function(n)sum(isPrime(unique(unlist(rle(primeFactors(n))))))
library(numbers)

Try it online!

Similar to Giuseppe (using numbers package and rle) but no assignments.

Improve this answer
\$\endgroup\$
4
  • 1
    \$\begingroup\$ Nice to see a golf in R. Feel free to put your answer up in the language of the month thread. \$\endgroup\$
    – Razetime
    Commented Sep 20, 2020 at 5:45
  • \$\begingroup\$ Thank you @Razetime. I don't have enough reputation to edit the community wiki post, but you may feel free to add the entry for me! \$\endgroup\$
    – user8617947
    Commented Sep 20, 2020 at 6:48
  • \$\begingroup\$ Note that you don't need to include the code that gives a name to your function in the byte-count (unless this is required for the function to run), so you can make it 1-byte shorter: Try it. \$\endgroup\$
    – Dominic van Essen
    Commented Sep 20, 2020 at 14:26
  • \$\begingroup\$ Thanks for the tip, @DominicvanEssen. \$\endgroup\$
    – user8617947
    Commented Sep 20, 2020 at 18:29
4
\$\begingroup\$

MATL, 8 bytes

&YFhuZpz

Try it online!

Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Gaia, 6 bytes

ḋ_uṗ¦Σ

Try it online!

  • ḋ computes the prime factorization, as [prime, exponent] pairs.

  • _ flattens the list.

  • u removes duplicate elements.

  • ṗ¦ maps through the elements and returns 1 if a prime is found, 0 otherwise.

  • Σ sums the list.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

CJam (13 bytes)

{mFe__&:mp1b}

Online test suite

This is pretty straightforward: get primes with multiplicities, reduce to distinct values, filter primes, count.

Sadly Martin pointed out some cases which weren't handled by the mildly interesting trick in my original answer, although he did also provide a 1-byte saving by observing that since mp gives 0 or 1 it can be mapped rather than filtered.

Improve this answer
\$\endgroup\$
0
2
\$\begingroup\$

Ohm v2, 6 5 bytes

-1 byte thanks to @Mr.Xcoder

ä{UpΣ

Try it online!

Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ 5 bytes: ä{UpΣ \$\endgroup\$
    – Mr. Xcoder
    Commented Oct 9, 2017 at 17:12
  • \$\begingroup\$ @Mr.Xcoder Thanks! I was looking for that built-in but wasn't able to find it.. \$\endgroup\$
    – Cinaski
    Commented Oct 10, 2017 at 7:17
2
+100
\$\begingroup\$

APL (Dyalog Unicode) + dfns, 29 bytes

⎕CY'dfns'
{≢∪⍵/⍨1pco⍵}∘∊2pco⊢

Try it online!

-6 bytes from Adám.

Explanation

{≢∪⍵/⍨1pco⍵}∘∊2pco⊢ ⊢ → input
                2pco  prime factors and exponents as matrix
{            }∘∊      flatten and use as right arg for:
    ⍵/⍨              filter out values in arg
        1pco⍵         which aren't prime
 ≢∪                   count the unique values
Improve this answer
\$\endgroup\$
0
1
\$\begingroup\$

Actually, 7 bytes

w♂i╔♂pΣ

Try it online!

Explanation:

w♂i╔♂pΣ
w        factor into [prime, exponent] pairs
 ♂i      flatten to 1D list
   ╔     unique elements
    ♂p   for each element: 1 if prime else 0
      Σ  sum
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Python 2, 142 135 119 bytes

f=lambda n,d=2:n-1and(n%d and f(n,d+1)or[d]+f(n/d))or[]
p=f(input())
print sum(f(n)==[n]for n in set(p+map(p.count,p)))

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Husk,  11  10 bytes

#ṗuS+omLgp

Try it online!

EDIT: Saved 1 byte thanks to Zgarb.

Improve this answer
\$\endgroup\$
1
  • 1
    \$\begingroup\$ #ṗuS+omLgp saves a byte. \$\endgroup\$
    – Zgarb
    Commented Oct 9, 2017 at 15:22
1
\$\begingroup\$

Brachylog, 7 bytes

ḋọcdṗˢl

Try it online!

           The output
      l    is the length of
  c        the concatenated
 ọ         list of pairs [value, number of occurrences]
ḋ          from the prime factorization of
           the input
   d       with duplicates removed
    ṗˢ     and non-primes removed.

A fun 9-byte version: ḋọ{∋∋ṗ}ᶜ¹

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Ruby -rprime, 66 bytes

->n{Prime.prime_division(n).flatten.uniq.count{|i|Prime.prime? i}}

Try it online!

Improve this answer
\$\endgroup\$
1
1
\$\begingroup\$

Japt, 11 bytes

k
âUü ml)èj

Try it

Alternative

k
â¡x¶X})xj

Try it

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Husk, 9 bytes

#ṗuṁS:Lgp

Try it online!

Slight improvement over Mr. XCoder's answer.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Vyxal s, 37 bitsv2, 4.625 bytes

ǐĊfUæ

Try it Online!'

Takes the counts of the prime factorization which gives a list of [prime, exponent] for each prime, flattens, uniquifies, finds the primes.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

Maxima, 104 bytes

So long, it can be golfed much more.

Try it online!

f(n):=lreduce(lambda([x,y],x+y),map(lambda([x],if primep(x)then 1 else 0),unique(flatten(ifactors(n)))))
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Pyth, 15 bytes

smP_d{+PQlM.gkP

Try it here!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

R + numbers, 92 bytes

function(n)sum(1|unique((x=c((r=rle(primeFactors(n)))$l,r$v))[isPrime(x)]))
library(numbers)

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

J, 20 bytes

3 :'+/1 p:~.,__ q:y'

Counted by hand lol, so tell me if this is off.

Any golfing suggestions?

Boring submission: flatten the prime factorization table and count primes.

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 47 bytes

n->#Set(select(isprime,concat(Vec(factor(n)))))

Try it online!

Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Javascript (ES6), 145 bytes

n=>{for(a=[b=l=0],q=n,d=2;q>=2;)q%d?(b&&(a.push(0),l++),d++,b=0):(q/=d,a[l]++,b=1);for(i in a){for(d=1,e=a[i];e%d;d++);e-d||n%e&&l++};return l+1}
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Factor, 62 bytes

group-factors flatten unique values [ prime? ] filter length ;

Attempt This Online!

Improve this answer
\$\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.