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

0
\$\begingroup\$

Python 3 + primefac, 50 bytes

from primefac import*
lambda n:len({*primefac(n)})

Python 2 + primefac, 52 bytes

from primefac import*
lambda n:len(set(primefac(n)))

Try it online

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

Python 2, 50 bytes

f=lambda n,k=2,p=1:n/k and(n%k<p%k)+f(n,k+1,p*k*k)

Try it online!

\$\endgroup\$
-2
\$\begingroup\$
import sys

X=int(sys.argv[1])
print X
b=2
a=0

while(b<X or b==X):
        if(X%b == 0):
                a=a+1;
                while(X%b==0):
                        X=X/b;
                b=b+1;
        else:
                b=b+1;

print a;
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! Could you specify language and bytecount? \$\endgroup\$ – Stephen Oct 9 '17 at 15:42
  • \$\begingroup\$ Looks like Python 2. \$\endgroup\$ – mbomb007 Oct 9 '17 at 19:29

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.