How many unique primes?

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.

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!

• So many prime questions recently! I love it. – Giuseppe Oct 8 '17 at 0:24
• Related – Mr. Xcoder Oct 8 '17 at 9:07
• 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 – Mr. Xcoder Oct 8 '17 at 13:36
• 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. – Gryphon Oct 8 '17 at 14:29
• 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. – Dennis Oct 9 '17 at 19:20

MATL, 4 3 bytes

-1 byte thanks to Luis Mendo

YFz


Try it online!

YF         Exponents of prime factors
z        Number of nonzeros


Yfun


Try it online!

A verYfun answer.

          (Implicit input)
Yf         Prime factorization
u        Unique
n       Numel
(Implicit output)

• Why fun? -- ;-) – Adám Oct 9 '17 at 19:40
• Crossed out 4 is still regular 4 – Gryphon Oct 10 '17 at 23:31

05AB1E, 2 bytes

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


Mathematica, 7 bytes

PrimeNu


Yup, there's a built-in.

Mathematica, 21 bytes

Length@*FactorInteger


The long way around.

• What's the reason for the asterisk? Isn't Length@FactorInteger the same? – numbermaniac Oct 10 '17 at 3:58
• 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. – Misha Lavrov Oct 10 '17 at 4:00

Gaia, 2 bytes

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

ḋl


Try it online!

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

• l - Length.

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]

• Is this a port of Dennis' answer here perchance? – Jonathan Allan Oct 8 '17 at 12:29
• @JonathanAllan Yes, modified to count unique prime factors instead. – orlp Oct 8 '17 at 12:30

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.

(?!(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. Bash + GNU utilities, 33 • 1 byte saved thanks to @Dennis factor|grep -Po ' \d+'|uniq|wc -l  Explanation factor| # Split input into prime factors grep -Po ' \d+'| # group factors onto lines uniq| # remove duplicates wc -l # count the lines  • grep -Po ' \d+' saves a byte over tr \ \\n|sed 1d. – Dennis Oct 9 '17 at 18:48 • Unfortunately, grep -Po '( \d+)\1*' fails for input 46. – Dennis Oct 10 '17 at 1:04 • @Dennis thanks - I fixed it using your original suggestion – Digital Trauma Oct 11 '17 at 20:53 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  • How did you miss Æv? – my pronoun is monicareinstate Oct 8 '17 at 8:19 • It was easy - I've never had a use for it and didn't search the list on the wiki. – Jonathan Allan Oct 8 '17 at 10:15 • How do you type jelly characters without atoms list and quicks list? – my pronoun is monicareinstate Oct 8 '17 at 10:16 • 1. Æ is alt code 0198. 2. You can set up a keyboard (I have not). 3. The code page. – Jonathan Allan Oct 8 '17 at 10:19 Ohm v2, 2 bytes ml  Try it online! The two built-ins are right next to each other in the documentation lol. Jelly, 2 bytes Yet another pretty boring answer... --- J. Allan Æv  Try it online! A built-in. 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.  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 • Would you mind writing an explanation for this answer? It seems to use an usual approach from the rest of the answers. – SEJPM Oct 8 '17 at 10:13 • @SEJPM i added some explanation there – DanielIndie Oct 8 '17 at 11:36 • FYI we may assume infinite call stacks / infinite resources for the majority of code-golf challenges (basically unless the question states otherwise). – Jonathan Allan Oct 8 '17 at 19:20 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. Explanation { } e# Define block mF e# List of (prime, exponent) pairs , e# Length  Brachylog, 3 bytes ḋdl  Try it online! Explanation ḋ Prime decomposition d Remove duplicates l Length  Pyth, 3 bytes l{P  Test suite Length (l) of set ({) of prime factors (P) of the input. Husk, 3 bytes Lup  Try it online! Explanation  p -- prime factors u -- unique elements L -- length  Actually, 2 bytes Yet another pretty boring answer... --- J. Allan yl  Try it online! The first character can be replaced by w. • That's enough, dude... :P – totallyhuman Oct 8 '17 at 5:36 • @icrieverytim I promise this is my last golfing-language answer (I only have 4 :P) – Mr. Xcoder Oct 8 '17 at 5:37 Pyke, 3 bytes P}l  Try it here! 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! R + numbers, 30 14 bytes 16 bytes removed thanks to @Giuseppe numbers::omega  Also, here is the Try it online!! link per @Giuseppe. • 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. – Giuseppe Oct 9 '17 at 19:56 • @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). – Joseph Wood Oct 9 '17 at 20:04 • NP, feel free to ping me in chat or comment on an answer of mine if you have questions. – Giuseppe Oct 9 '17 at 21:15 • @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. – BLT Oct 9 '17 at 22:52 • (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. – BLT Oct 9 '17 at 22:53 Convex, 3 bytes mF,  Try it online! Pari/GP, 5 bytes I don't know why it is called nu in Mathematica but omega in Pari/GP. omega  Try it online! 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  • You can use sum[1|x<- ... ] instead of length. – Laikoni Oct 8 '17 at 10:17 Japt, 5 4 bytes â èj  Try it Get the divisors (â) and count (è) the primes (j). ARBLE, 28 bytes len(unique(primefactors(n)))  Try it online! This is a very literal solution • 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?! – totallyhuman Oct 9 '17 at 22:08 • @icrieverytim Congratulations, you have discovered one of the main reasons this language exists. – ATaco Oct 9 '17 at 22:12 Dyalog APL, 17 bytes ⎕CY'dfns' ≢∪3pco⎕  Try it online! 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. • – Jonathan Frech Oct 8 '17 at 13:39 • @JonathanFrech Thanks, that is much cleaner. – Jonathan Allan Oct 8 '17 at 19:15 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!

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!

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")`