# Primes in the prime factorisation

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\$$.

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!

• 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)? Oct 9, 2017 at 12:38
• 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. Oct 9, 2017 at 12:55
• You claim this is not an OEIS sequence. Is it not A001221, the values of the (small) omega function? Oct 10, 2017 at 9:39
• 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. Oct 10, 2017 at 10:59
• 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... Oct 10, 2017 at 13:45

# Jelly,  9  7 bytes

ÆFFQÆPS


## 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.


# Mathematica, 39 bytes

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


Try it online!

thanks to Martin Ender (-11 bytes)

• 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) Oct 9, 2017 at 13:53
• How about Count[Union@@FactorInteger@#,_?PrimeQ]&? (Haven't checked all test cases.) Oct 9, 2017 at 17:36
• @MartinEnder seems like it should work. Passes all test cases too. Oct 10, 2017 at 0:30

# 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

• -1 byte by using €pO after merging the prime factors and exponents: ÓsfìÙ€pO May 6, 2019 at 10:59
• @KevinCruijssen: Thanks! Actually saves 2 since € isn't needed. May 6, 2019 at 11:27
• Ah, of course.. Wow, not sure how I missed that, haha xD May 6, 2019 at 11:28

# 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.

• Nice to see a golf in R. Feel free to put your answer up in the language of the month thread. Sep 20, 2020 at 5:45
• 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! Sep 20, 2020 at 6:48
• 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. Sep 20, 2020 at 14:26
• Thanks for the tip, @DominicvanEssen. Sep 20, 2020 at 18:29

# MATL, 8 bytes

&YFhuZpz


Try it online!

# 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.

## 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.

# Ohm v2, 6 5 bytes

-1 byte thanks to @Mr.Xcoder

ä{UpΣ


Try it online!

• 5 bytes: ä{UpΣ Oct 9, 2017 at 17:12
• @Mr.Xcoder Thanks! I was looking for that built-in but wasn't able to find it.. Oct 10, 2017 at 7:17

# APL (Dyalog Unicode) + dfns, 29 bytes

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


Try it online!

## 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


# 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


# Python 2, 142135 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!

# Husk,  11  10 bytes

#ṗuS+omLgp


Try it online!

EDIT: Saved 1 byte thanks to Zgarb.

• #ṗuS+omLgp saves a byte. Oct 9, 2017 at 15:22

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

# Ruby-rprime, 66 bytes

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


Try it online!

# Japt, 11 bytes

k
âUü ml)èj


Try it

## Alternative

k
â¡x¶X})xj


Try it

# Husk, 9 bytes

#ṗuṁS:Lgp


Try it online!

Slight improvement over Mr. XCoder's answer.

# Vyxals, 37 bitsv2, 4.625 bytes

ǐĊfUæ


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

# 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)))))


# Pyth, 15 bytes

smP_d{+PQlM.gkP


Try it here!

# 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!

# 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.

# Pari/GP, 47 bytes

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


Try it online!

# 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}


# Factor, 62 bytes

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


Attempt This Online!