14
\$\begingroup\$

One way to represent a natural number is by multiplying exponents of prime numbers. For example, 6 can be represented by 2^1*3^1, and 50 can be represented by 2^1*5^2 (where ^ indicates exponention). The number of primes in this representation can help determine whether it is shorter to use this method of representation, compared to other methods. But because I don't want to calculate these by hand, I need a program to do it for me. However, because I'll have to remember the program until I get home, it needs to be as short as possible.

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 input, as outlined in the introduction.

Test Cases:

24      -> 2 (2^3*3^1)
126     -> 3 (2^1*3^2*7^1)
1538493 -> 4 (3^1*11^1*23^1*2027^1)
123456  -> 3 (2^6*3^1*643^1)

This is OEIS A001221.

Scoring:

This is , lowest score in bytes wins!

\$\endgroup\$
  • 3
    \$\begingroup\$ So many prime questions recently! I love it. \$\endgroup\$ – Giuseppe Oct 8 '17 at 0:24
  • 2
    \$\begingroup\$ Related \$\endgroup\$ – Mr. Xcoder Oct 8 '17 at 9:07
  • 3
    \$\begingroup\$ The reason behind the downvote might be its triviality. As far as I could see, there are 3 situations when it comes to golfing languages : 1. built-in 2. chain of two built-ins 3. chain of 3 built-ins (I personally have three 2-byte answers); I don't know if that is a solid reason for a downvote, but it is a possible cause \$\endgroup\$ – Mr. Xcoder Oct 8 '17 at 13:36
  • 1
    \$\begingroup\$ Could be, but I would appreciate if one of the three downvoters would have commented telling me that. While it is trivial in golfing languages, there are a few interesting solutions in non golfing languages, which are the ones I wanted to see when I posted this challenge. After all, there are many challenges on the site which are trivial for golflangs, but produce interesting non-golflang solutions. \$\endgroup\$ – Gryphon Oct 8 '17 at 14:29
  • 1
    \$\begingroup\$ It would beneficial to include a prime in the test cases. Also, some languages/approaches are hard to test for large numbers. A few smaller test cases would be nice. \$\endgroup\$ – Dennis Oct 9 '17 at 19:20

33 Answers 33

6
\$\begingroup\$

MATL, 4 3 bytes

-1 byte thanks to Luis Mendo

YFz

Try it online!

YF         Exponents of prime factors
  z        Number of nonzeros

Original answer:

Yfun

Try it online!

A verYfun answer.

          (Implicit input)
Yf         Prime factorization
  u        Unique
   n       Numel
           (Implicit output)
\$\endgroup\$
  • 1
    \$\begingroup\$ Why fun? -- ;-) \$\endgroup\$ – Adám Oct 9 '17 at 19:40
  • 1
    \$\begingroup\$ Crossed out 4 is still regular 4 \$\endgroup\$ – Gryphon Oct 10 '17 at 23:31
5
\$\begingroup\$

05AB1E, 2 bytes

another pretty boring answer...

fg

A full program accepting a numeric input and printing the result

Try it online!

How?

fg - implicitly take input
f  - get the prime factors with no duplicates
 g - get the length
   - implicit print
\$\endgroup\$
5
\$\begingroup\$

Mathematica, 7 bytes

PrimeNu

Yup, there's a built-in.

Mathematica, 21 bytes

Length@*FactorInteger

The long way around.

\$\endgroup\$
  • \$\begingroup\$ What's the reason for the asterisk? Isn't Length@FactorInteger the same? \$\endgroup\$ – numbermaniac Oct 10 '17 at 3:58
  • 1
    \$\begingroup\$ Length@*FactorInteger produces a pure function: the composition of Length and FactorInteger. I can define fun=Length@*FactorInteger and then call fun[1001]. On the other hand, Length@FactorInteger would mean Length[FactorInteger] and evaluate to 0. \$\endgroup\$ – Misha Lavrov Oct 10 '17 at 4:00
5
\$\begingroup\$

Gaia, 2 bytes

Yet another pretty boring answer... --- J. Allan

ḋl

Try it online!

  • - Prime factorization as [prime, exponent] pairs.

  • l - Length.

\$\endgroup\$
4
\$\begingroup\$

Python 2, 56 bytes

f=lambda n,p=2,k=1:n/p and[f(n,p+1),k+f(n/p,p,0)][n%p<1]
\$\endgroup\$
  • \$\begingroup\$ Is this a port of Dennis' answer here perchance? \$\endgroup\$ – Jonathan Allan Oct 8 '17 at 12:29
  • 1
    \$\begingroup\$ @JonathanAllan Yes, modified to count unique prime factors instead. \$\endgroup\$ – orlp Oct 8 '17 at 12:30
4
\$\begingroup\$

Retina, 31 30 bytes

&`(?!(11+)\1+$)(11+)$(?<=^\2+)

Input is in unary.

Thanks to @MartinEnder for golfing of 1 byte!

Try it online! (includes decimal-to-unary converter)

How it works

Since the program consists of a single regex with the & modifier, Retina simply counts the amount of overlapping matches. The input is assumed to consist of n repetitions of 1 and nothing else.

The negative lookahead

(?!(11+)\1+$)

matches at locations between 1's that are not followed by two or more 1's (11+), followed by one or more repetitions of the same amount of 1's (\1+), followed by the end of input ($).

Any composite number ab with a, b > 1 can be written as b repetitions of a repetitions of 1, so the lookahead matches only locations followed by p repetitions of 1, where p = 1 or p is prime.

The regex

(11+)$

makes sure p > 1 by requiring at least two 1's (11+) and stores the tail of 1's in the second capture group (\2).

Finally, the positive lookbehind

(?<=^\2+)

verifies that the entire input consists of kp occurrences (k ≥ 1) of 1, verifying that p divides the input.

Thus, each match corresponds to a unique prime divisor p.

\$\endgroup\$
4
\$\begingroup\$

Bash + GNU utilities, 33

  • 1 byte saved thanks to @Dennis
factor|grep -Po ' \d+'|uniq|wc -l

Try it online.

Explanation

factor|                            # Split input into prime factors
       grep -Po ' \d+'|            # group factors onto lines
                       uniq|       # remove duplicates
                            wc -l  # count the lines
\$\endgroup\$
  • 1
    \$\begingroup\$ grep -Po ' \d+' saves a byte over tr \ \\n|sed 1d. \$\endgroup\$ – Dennis Oct 9 '17 at 18:48
  • \$\begingroup\$ Unfortunately, grep -Po '( \d+)\1*' fails for input 46. \$\endgroup\$ – Dennis Oct 10 '17 at 1:04
  • \$\begingroup\$ @Dennis thanks - I fixed it using your original suggestion \$\endgroup\$ – Digital Trauma Oct 11 '17 at 20:53
3
\$\begingroup\$

Jelly, 3 bytes

a pretty boring answer...

ÆFL

A monadic link taking a number and returning a number

Try it online!

How?

ÆFL - Link: number, n
ÆF  - prime factorisation as a list of prime, exponent pairs
  L - length
\$\endgroup\$
  • 1
    \$\begingroup\$ How did you miss Æv? \$\endgroup\$ – someone Oct 8 '17 at 8:19
  • \$\begingroup\$ It was easy - I've never had a use for it and didn't search the list on the wiki. \$\endgroup\$ – Jonathan Allan Oct 8 '17 at 10:15
  • \$\begingroup\$ How do you type jelly characters without atoms list and quicks list? \$\endgroup\$ – someone Oct 8 '17 at 10:16
  • \$\begingroup\$ 1. Æ is alt code 0198. 2. You can set up a keyboard (I have not). 3. The code page. \$\endgroup\$ – Jonathan Allan Oct 8 '17 at 10:19
3
\$\begingroup\$

Ohm v2, 2 bytes

ml

Try it online!

The two built-ins are right next to each other in the documentation lol.

\$\endgroup\$
3
\$\begingroup\$

Jelly, 2 bytes

Yet another pretty boring answer... --- J. Allan

Æv

Try it online!

A built-in.

\$\endgroup\$
3
\$\begingroup\$

Alice, 10 bytes

/o
\i@/Dcd

Try it online!

Explanation

/o
\i@/...

This is just the standard framework for linear arithmetic-heavy programs that need decimal I/O. The actual program itself is then just:

Dcd

Which does:

D    Deduplicate prime factors. Does what it sounds like: for every p^k which
     is a divisor n, this divides n by p^(k-1).
c    Push the individual prime factors of n. Since we've deduplicated them
     first, the number of factors is equal to the value we're looking for.
d    Push the stack depth, i.e. the number of unique prime factors.
\$\endgroup\$
3
\$\begingroup\$

JavaScript 45 bytes

*For @SEJPM request an explanation : what im doing here is this- im going from 2 - n (which changes, and eventually will be the biggest prime factor)- now if the current number divide n i want to count it only once(even though it can be a factor of 2*2*2*3 - 2 is counted once)- so the "j" comes to the picture, when j is not specified in the call of the funcion - j will receive the value of "undefined" , and when n%i == 0 then i call the function with j=1 in the next call) - and then i only add 1 when j equals undefined which is !j + Function(n/i,i,(j=1 or just 1)). i dont change i in this matter becuase it may still be divisible by i again(2*2*3) but then j will equal 1 and it will not count as a factor. hope i explained it well enough.

P=(n,i=2,j)=>i>n?0:n%i?P(n,i+1):!j+P(n/i,i,1)

console.log(P(1538493)==4);
console.log(P(24)==2);
console.log(P(126)==3);
console.log(P(123456)==3);

if the last prime is very big than it will have max call stack- if its an issue i can make an iterative one

\$\endgroup\$
  • \$\begingroup\$ Would you mind writing an explanation for this answer? It seems to use an usual approach from the rest of the answers. \$\endgroup\$ – SEJPM Oct 8 '17 at 10:13
  • \$\begingroup\$ @SEJPM i added some explanation there \$\endgroup\$ – DanielIndie Oct 8 '17 at 11:36
  • 1
    \$\begingroup\$ FYI we may assume infinite call stacks / infinite resources for the majority of code-golf challenges (basically unless the question states otherwise). \$\endgroup\$ – Jonathan Allan Oct 8 '17 at 19:20
3
\$\begingroup\$

CJam, 7 5 bytes

Thanks to Martin Ender for 2 bytes off!

{mF,}

Anonymous block (function) that expects the input number on the stack and replaces it by the output number.

Try it online! Or verify all test cases.

Explanation

{   }   e# Define block
 mF     e# List of (prime, exponent) pairs
   ,    e# Length
\$\endgroup\$
3
\$\begingroup\$

Brachylog, 3 bytes

ḋdl

Try it online!

Explanation

ḋ      Prime decomposition
 d     Remove duplicates
  l    Length
\$\endgroup\$
2
\$\begingroup\$

Pyth, 3 bytes

l{P

Test suite

Length (l) of set ({) of prime factors (P) of the input.

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

Husk, 3 bytes

Lup

Try it online!

Explanation

  p  -- prime factors
 u   -- unique elements
L    -- length
\$\endgroup\$
2
\$\begingroup\$

Actually, 2 bytes

Yet another pretty boring answer... --- J. Allan

yl

Try it online!

The first character can be replaced by w.

\$\endgroup\$
  • \$\begingroup\$ That's enough, dude... :P \$\endgroup\$ – totallyhuman Oct 8 '17 at 5:36
  • \$\begingroup\$ @icrieverytim I promise this is my last golfing-language answer (I only have 4 :P) \$\endgroup\$ – Mr. Xcoder Oct 8 '17 at 5:37
2
\$\begingroup\$

Pyke, 3 bytes

P}l

Try it here!

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

Python 3, 68 67 bytes

1 byte removed thanks to @Mr.Xcoder

lambda n:sum(n%k<all(k%j for j in range(2,k))for k in range(2,n+1))

This times out for the largest test cases. Try it online!

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

R + numbers, 30 14 bytes

16 bytes removed thanks to @Giuseppe

numbers::omega

Also, here is the Try it online!! link per @Giuseppe.

\$\endgroup\$
  • \$\begingroup\$ You may omit the f=function(x) and the (x) as numbers::omega is a function already. However, as numbers is not standard for R, you should make your answer "R + numbers". Also, you should include a TIO link. Still, +1, very nice. \$\endgroup\$ – Giuseppe Oct 9 '17 at 19:56
  • \$\begingroup\$ @Giuseppe, you are too nice. Thanks for your help. BTW, in addition to some of your insightful answers, I checked out Tips for golfing in R, as you suggested. There are some real gems there. Anywho, I will update my answer with your recommendations. Also, your MATL solution is very nice (+1 yesterday). \$\endgroup\$ – Joseph Wood Oct 9 '17 at 20:04
  • \$\begingroup\$ NP, feel free to ping me in chat or comment on an answer of mine if you have questions. \$\endgroup\$ – Giuseppe Oct 9 '17 at 21:15
  • \$\begingroup\$ @Giuseppe is there a meta consensus on needing to explicitly state "R + numbers"? It seems like if we state the additional package then we should be able to save the bytes of explicitly calling it with numbers::. Otherwise, to me it's the same as using an import in any other language. \$\endgroup\$ – BLT Oct 9 '17 at 22:52
  • \$\begingroup\$ (scrolls down and sees a python example of this...) I guess I'm wondering about a broader meta consensus, then. It just sort of seems silly to me. \$\endgroup\$ – BLT Oct 9 '17 at 22:53
1
\$\begingroup\$

Convex, 3 bytes

mF,

Try it online!

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

Pari/GP, 5 bytes

I don't know why it is called nu in Mathematica but omega in Pari/GP.

omega

Try it online!

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

Haskell, 58 bytes

-4 bytes thanks to @Laikoni

f n=sum[1|x<-[2..n],gcd x n>1,all((>)2.gcd x)[2..x-1]]

Try it online!

Explanation

Essentially generates all primes at most as large as n and filters them for being a factor of n and then takes the length of the result.

f n=                                                   -- main function
    sum[                                             ] -- output the length of the list
        1|x<-[2..n],                                   -- consider all potential primes <=n
                                                       -- and insert 1 into the list if predicates are satisfied
                    gcd x n>1,                         -- which are a factor of n
                              all(          )[2..x-1]  -- and for which all smaller numbers satisfy
                                  (>)2.                -- 2 being larger than
                                       gcd x           -- the gcd of x with the current smaller number
\$\endgroup\$
  • \$\begingroup\$ You can use sum[1|x<- ... ] instead of length. \$\endgroup\$ – Laikoni Oct 8 '17 at 10:17
1
\$\begingroup\$

Japt, 5 4 bytes

â èj

Try it

Get the divisors (â) and count (è) the primes (j).

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

ARBLE, 28 bytes

len(unique(primefactors(n)))

Try it online!

This is a very literal solution

\$\endgroup\$
  • \$\begingroup\$ I was looking at this and going "Hey, wait a minute, this is a snippet!" And then I see... is this supposed to be a non-esoteric language with implicit IO?! \$\endgroup\$ – totallyhuman Oct 9 '17 at 22:08
  • \$\begingroup\$ @icrieverytim Congratulations, you have discovered one of the main reasons this language exists. \$\endgroup\$ – ATaco Oct 9 '17 at 22:12
0
\$\begingroup\$

Dyalog APL, 17 bytes

⎕CY'dfns'
≢∪3pco⎕

Try it online!

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

Python 2,  63  55 bytes

A much more interesting answer...

-8 bytes thanks to Jonathan Frech (use an argument with a default for the post-adjustment of the result of primes from 0 to 1 -- much better than a wrapping lambda!!)

f=lambda n,o=1:sum(n%i+f(i,0)<1for i in range(2,n))or o

A recursive function taking a positive integer, n, and returning a positive integer, the count.

Try it online! Really inefficient, don't even bother with the other test cases.

\$\endgroup\$
  • \$\begingroup\$ 55 bytes. \$\endgroup\$ – Jonathan Frech Oct 8 '17 at 13:39
  • \$\begingroup\$ @JonathanFrech Thanks, that is much cleaner. \$\endgroup\$ – Jonathan Allan Oct 8 '17 at 19:15
0
\$\begingroup\$

J, 12 bytes

{:@$@(__&q:)

q: is J's prime exponents function, giving it the argument __ produces a matrix whose first row is all nonzero prime factors and whose 2nd row is their exponents.

We take the shape $ of that matrix -- rows by columns -- the number of columns is the answer we seek.

{: gives us the last item of this two items (num rows, num columns) list, and hence the answer.

Try it online!

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

Java (OpenJDK 9), 67 bytes

n->{int c=0,p=1;for(;p<n;)if(n%++p<1)for(c++;n%p<1;n/=p);return c;}

Try it online!

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

Javascript ES6, 56 chars

n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)

Test:

f=n=>eval(`for(q=2,r=0;q<=n;++q)n%q||(n/=q,r+=!!(n%q--))`)
console.log([24,126,1538493,123456].map(f)=="2,3,4,3")

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