15
\$\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\$
7
  • 3
    \$\begingroup\$ So many prime questions recently! I love it. \$\endgroup\$
    – Giuseppe
    Oct 8, 2017 at 0:24
  • 2
    \$\begingroup\$ Related \$\endgroup\$
    – Mr. Xcoder
    Oct 8, 2017 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, 2017 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, 2017 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, 2017 at 19:20

33 Answers 33

1
2
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\$
2
  • 1
    \$\begingroup\$ Welcome to PPCG! Could you specify language and bytecount? \$\endgroup\$
    – Stephen
    Oct 9, 2017 at 15:42
  • \$\begingroup\$ Looks like Python 2. \$\endgroup\$
    – mbomb007
    Oct 9, 2017 at 19:29
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.