How many unique primes?

Question

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 code-golf, lowest score in bytes wins!

Answer 1

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)

Answer 2

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

Answer 3

Mathematica, 7 bytes

PrimeNu

Yup, there's a built-in.

Mathematica, 21 bytes

Length@*FactorInteger

The long way around.

Answer 4

Gaia, 2 bytes

^{Yet another pretty boring answer... --- J. Allan}

ḋl

Try it online!

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

• l - Length.

Answer 5

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]

Answer 6

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.

Answer 7

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

Answer 8

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

Answer 9

Ohm v2, 2 bytes

ml

Try it online!

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

Answer 10

Jelly, 2 bytes

^{Yet another pretty boring answer... --- J. Allan}

Æv

Try it online!

A built-in.

Answer 11

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.

Answer 12

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

Answer 13

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

Answer 14

Brachylog, 3 bytes

ḋdl

Try it online!

Explanation

ḋ      Prime decomposition
 d     Remove duplicates
  l    Length

Answer 15

Pyth, 3 bytes

l{P

Test suite

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

Answer 16

Husk, 3 bytes

Lup

Try it online!

Explanation

  p  -- prime factors
 u   -- unique elements
L    -- length

Answer 17

Actually, 2 bytes

^{Yet another pretty boring answer... --- J. Allan}

yl

Try it online!

The first character can be replaced by w.

Answer 18

Pyke, 3 bytes

P}l

Try it here!

Answer 19

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!

Answer 20

R + numbers, 30 14 bytes

16 bytes removed thanks to @Giuseppe

numbers::omega

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

Answer 21

Convex, 3 bytes

mF,

Try it online!

Answer 22

Pari/GP, 5 bytes

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

omega

Try it online!

Answer 23

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

Answer 24

Japt, 5 4 bytes

â èj

Try it

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

Answer 25

ARBLE, 28 bytes

len(unique(primefactors(n)))

Try it online!

This is a very literal solution

Answer 26

Dyalog APL, 17 bytes

⎕CY'dfns'
≢∪3pco⎕

Try it online!

Answer 27

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.

Answer 28

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!

Answer 29

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!

Answer 30

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