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!

\$\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
    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
    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\$ 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
    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\$ Oct 10, 2017 at 13:45

24 Answers 24

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

Mathematica, 39 bytes

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

Try it online!

thanks to Martin Ender (-11 bytes)

\$\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\$ Oct 9, 2017 at 13:53
  • \$\begingroup\$ How about Count[Union@@FactorInteger@#,_?PrimeQ]&? (Haven't checked all test cases.) \$\endgroup\$ Oct 9, 2017 at 17:36
  • \$\begingroup\$ @MartinEnder seems like it should work. Passes all test cases too. \$\endgroup\$ 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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ -1 byte by using €pO after merging the prime factors and exponents: ÓsfìÙ€pO \$\endgroup\$ May 6, 2019 at 10:59
  • \$\begingroup\$ @KevinCruijssen: Thanks! Actually saves 2 since isn't needed. \$\endgroup\$
    – Emigna
    May 6, 2019 at 11:27
  • \$\begingroup\$ Ah, of course.. Wow, not sure how I missed that, haha xD \$\endgroup\$ 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.

\$\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
    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\$ 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\$ Sep 20, 2020 at 14:26
  • \$\begingroup\$ Thanks for the tip, @DominicvanEssen. \$\endgroup\$ Sep 20, 2020 at 18:29
4
\$\begingroup\$

MATL, 8 bytes

&YFhuZpz

Try it online!

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

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

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

Ohm v2, 6 5 bytes

-1 byte thanks to @Mr.Xcoder

ä{UpΣ

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ 5 bytes: ä{UpΣ \$\endgroup\$
    – Mr. Xcoder
    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
    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
\$\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
\$\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!

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

Husk,  11  10 bytes

#ṗuS+omLgp

Try it online!


EDIT: Saved 1 byte thanks to Zgarb.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ #ṗuS+omLgp saves a byte. \$\endgroup\$
    – Zgarb
    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: ḋọ{∋∋ṗ}ᶜ¹

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

Ruby -rprime, 66 bytes

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

Try it online!

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

Japt, 11 bytes

k
âUü ml)èj

Try it

Alternative

k
â¡x¶X})xj

Try it

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

Husk, 9 bytes

#ṗuṁS:Lgp

Try it online!

Slight improvement over Mr. XCoder's 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.

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

Pyth, 15 bytes

smP_d{+PQlM.gkP

Try it here!

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

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

\$\endgroup\$
0
\$\begingroup\$

Pari/GP, 47 bytes

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

Try it online!

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

Factor, 62 bytes

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

Attempt This Online!

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