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*3^1, and 50 can be represented by 2^1*5^2 (where ^ indicates exponention).

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 code-golf, lowest score in bytes wins!

pbeentje

Posted 2017-10-09T12:09:11.737

Reputation: 289

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)? – Emigna – 2017-10-09T12:38:01.493

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. – pbeentje – 2017-10-09T12:55:13.997

You claim this is not an OEIS sequence. Is it not A001221, the values of the (small) omega function? – Gray Taylor – 2017-10-10T09:39:06.643

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. – pbeentje – 2017-10-10T10:59:57.993

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... – Gray Taylor – 2017-10-10T13:45:53.903

Answers

Mathematica, 39 bytes

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

Try it online!

thanks to Martin Ender (-11 bytes)

J42161217

Posted 2017-10-09T12:09:11.737

Reputation: 15 931

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) – JungHwan Min – 2017-10-09T13:53:58.410

How about Count[Union@@FactorInteger@#,_?PrimeQ]&? (Haven't checked all test cases.) – Martin Ender – 2017-10-09T17:36:04.990

@MartinEnder seems like it should work. Passes all test cases too. – JungHwan Min – 2017-10-10T00:30:39.067

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

Emigna

Posted 2017-10-09T12:09:11.737

Reputation: 50 798

-1 byte by using €pO after merging the prime factors and exponents: ÓsfìÙ€pO

– Kevin Cruijssen – 2019-05-06T10:59:03.450

@KevinCruijssen: Thanks! Actually saves 2 since € isn't needed. – Emigna – 2019-05-06T11:27:16.007

Ah, of course.. Wow, not sure how I missed that, haha xD – Kevin Cruijssen – 2019-05-06T11:28:36.720

MATL, 8 bytes

&YFhuZpz

Try it online!

Cinaski

Posted 2017-10-09T12:09:11.737

Reputation: 1 588

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.

Mr. Xcoder

Posted 2017-10-09T12:09:11.737

Reputation: 39 774

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.

Mr. Xcoder

Posted 2017-10-09T12:09:11.737

Reputation: 39 774

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.

Peter Taylor

Posted 2017-10-09T12:09:11.737

Reputation: 41 901

Ohm v2, 6 5 bytes

-1 byte thanks to @Mr.Xcoder

ä{UpΣ

Try it online!

Cinaski

Posted 2017-10-09T12:09:11.737

Reputation: 1 588

5 bytes: ä{UpΣ

– Mr. Xcoder – 2017-10-09T17:12:39.863

@Mr.Xcoder Thanks! I was looking for that built-in but wasn't able to find it.. – Cinaski – 2017-10-10T07:17:16.903

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

Mego

Posted 2017-10-09T12:09:11.737

Reputation: 32 998

Husk, 11 10 bytes

#ṗuS+omLgp

Try it online!

EDIT: Saved 1 byte thanks to Zgarb.

Mr. Xcoder

Posted 2017-10-09T12:09:11.737

Reputation: 39 774

1#ṗuS+omLgp saves a byte. – Zgarb – 2017-10-09T15:22:14.423

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!

ovs

Posted 2017-10-09T12:09:11.737

Reputation: 21 408

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: ḋọ{∋∋ṗ}ᶜ¹

Unrelated String

Posted 2017-10-09T12:09:11.737

Reputation: 5 300

Ruby `-rprime`, 66 bytes

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

Try it online!

Kirill L.

Posted 2017-10-09T12:09:11.737

Reputation: 6 693

49 bytes by using the builtin functions added to the number classes when prime is imported – Value Ink – 2019-09-05T21:55:20.807

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!

Giuseppe

Posted 2017-10-09T12:09:11.737

Reputation: 21 077

Pyth, 15 bytes

smP_d{+PQlM.gkP

Try it here!

Mr. Xcoder

Posted 2017-10-09T12:09:11.737

Reputation: 39 774

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.

cole

Posted 2017-10-09T12:09:11.737

Reputation: 3 526

Pari/GP, 47 bytes

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

Try it online!

alephalpha

Posted 2017-10-09T12:09:11.737

Reputation: 23 988

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}

Naruyoko

Posted 2017-10-09T12:09:11.737

Reputation: 459

Primes in the prime factorisation

Your task:

Input:

Output:

Test cases:

Scoring:

Answers

Mathematica, 39 bytes

05AB1E, 9 7 bytes

MATL, 8 bytes

Jelly, 9 7 bytes

How?

Gaia, 6 bytes

CJam (13 bytes)

Ohm v2, 6 5 bytes

Actually, 7 bytes

Husk, 11 10 bytes

Python 2, 142 135 119 bytes

Brachylog, 7 bytes

Ruby -rprime, 66 bytes

R + numbers, 92 bytes

Pyth, 15 bytes

J, 20 bytes

Pari/GP, 47 bytes

Javascript (ES6), 145 bytes

Ruby `-rprime`, 66 bytes