StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>First, do you mean find the total number of divisors, the number of primes in its factorization, or the number of distinct prime divisors? For instance, 12 = 2 * 2 * 3 has 6 divisors (1,2,3,4,6,12), 3 primes in its factorization (2,2,3), and 2 distinct prime divisors (2,3). Do you want 6, 3, or 2 as your result? I'm going to assume you want the second of these for the rest of this, but I don't think anything materially changes if you were interested in one of the others...</p> <p>Second, you're going to have to fully factor your number. There is no known shortcut that can find the number of prime factors without finding the factors themselves. (With the notable exception that you can test whether the number of factors is ==1 or >=2 quickly.)</p> <p>10^12 is not that big. You only need to test divisors up to the square root of the number, which is at most 10^6. Say a divide takes 20 cycles on a modern CPU at 2GHz, that's only 10 milliseconds to test a million divisors.</p> <pre><code>#include <stdio.h> #include <stdlib.h> int main(int argc, char *argv[]) { long long n = atoll(argv[1]); for (int i = 2; i < 1000000; i++) { while (n % i == 0) { printf("%d\n", i); n /= i; } } if (n > 1) printf("%lld\n", n); } </code></pre> <p>Takes 23 milliseconds on my machine. Wonder where that other 13 milliseconds went?</p> <p>Python is about 10x slower, as this code still takes only 0.23 seconds on my machine:</p> <pre><code>import sys n = int(sys.argv[1]) for i in xrange(2, 1000000): while n%i==0: print i; n/=i if n>1: print n </code></pre> <p>How fast do you want it?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload