9
\$\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*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 , lowest score in bytes wins!

\$\endgroup\$
  • \$\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 '17 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 '17 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 Oct 10 '17 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 '17 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 Oct 10 '17 at 13:45

17 Answers 17

5
\$\begingroup\$

Mathematica, 39 bytes

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

Try it online!

thanks to Martin Ender (-11 bytes)

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

MATL, 8 bytes

&YFhuZpz

Try it online!

\$\endgroup\$
4
\$\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\$
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\$
2
\$\begingroup\$

Ohm v2, 6 5 bytes

-1 byte thanks to @Mr.Xcoder

ä{UpΣ

Try it online!

\$\endgroup\$
  • \$\begingroup\$ 5 bytes: ä{UpΣ \$\endgroup\$ – Mr. Xcoder Oct 9 '17 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 '17 at 7:17
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
    \$\begingroup\$ #ṗuS+omLgp saves a byte. \$\endgroup\$ – Zgarb Oct 9 '17 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\$
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\$

Ruby -rprime, 66 bytes

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

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.