Find as fast as possible complete divisors of a number up to 10 ^ 12?

Question

I need to calculate the total number of divisors of the number N (without worrying about what the values ​​of the divisors are) and do it within 40-80 operations for all such numbers N. How can I do this? This is not a homework question. I tried the Pollard Rho algorithm, but even that turned out to be too slow for my purposes. Here is my python code. How can I improve my work, if possible?

def is_prime(n): if n < 2: return False ps = [2,3,5,7,11,13,17,19,23,29,31,37,41, 43,47,53,59,61,67,71,73,79,83,89,97] def is_spsp(n, a): d, s = n-1, 0 while d%2 == 0: d /= 2; s += 1 t = pow(int(a),int(d),int(n)) if t == 1: return True while s > 0: if t == n-1: return True t = (t*t) % n s -= 1 return False if n in ps: return True for p in ps: if not is_spsp(n,p): return False return True def gcd(a,b): while b: a, b = b, a%b return abs(a) def rho_factors(n, limit=100): def gcd(a,b): while b: a, b = b, a%b return abs(a) def rho_factor(n, c, limit): f = lambda x: (x*x+c) % n t, h, d = 2, 2, 1 while d == 1: if limit == 0: raise OverflowError('limit exceeded') t = f(t); h = f(f(h)); d = gcd(th, n) if d == n: return rho_factor(n, c+1, limit) if is_prime(d): return d return rho_factor(d, c+1, limit) if -1 <= n <= 1: return [n] if n < -1: return [-1] + rho_factors(-n, limit) fs = [] while n % 2 == 0: n = n // 2; fs = fs + [2] if n == 1: return fs while not is_prime(n): f = rho_factor(n, 1, limit) n = int(n / f) fs = fs + [f] return sorted(fs + [n]) def divs(n): if(n==1): return 1 ndiv=1 f=rho_factors(n) l=len(f) #print(f) c=1 for x in range(1,l): #print(f[x]) if(f[x]==f[x-1]): c=c+1 else: ndiv=ndiv*(c+1) c=1 # print ("C",c,"ndiv",ndiv) ndiv=ndiv*(c+1) return ndiv 

Answer 1

I remember how to solve this problem earlier on SPOJ, but I don’t remember the exact method I used (it would be great if you provided the identifier of the problem). Have you tried the naive method here? It has complexity O(sqrt n) , which in <xy> has value O(10 ^ 6) . The modulo statement may be a little slow, but worth a try. Here's what it should look like when done in C ++:

 int cntdiv = 0; for(int i = 2; i * i <= x; i ++) { if(x % i == 0) { cntdiv += 1 + (i * i != x); } } //cntdiv is now your count 

Answer 2

First, do you mean finding the total number of divisors, the number of primes in its factorization, or the number of different prime divisors? For example, 12 = 2 * 2 * 3 has 6 divisors (1,2,3,4,6,12), 3 simple factors in its factorization (2,2,3) and 2 different simple divisors (2,3), you want 6, 3 or 2 as a result? I'm going to suggest that you want the second one for the rest of this, but I don’t think that something will materially change if you are interested in one of the others ...

Secondly, you will need to fully indicate your number. An unknown label that can find the number of simple factors without finding the factors themselves. (Except that you can check if the number of factors is really == 1 or> = 2.)

10 ^ 12 is not so great. You only need to check the divisors to the square root of a number that is not more than 10 ^ 6. Let's say that the separation takes 20 cycles on a modern processor at a frequency of 2 GHz, which is only 10 milliseconds, to test a million dividers.

 #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); } 

It takes 23 milliseconds on my machine. I wonder where the other 13 milliseconds went?

Python is about 10 times slower since this code still only takes 0.23 seconds on my machine:

 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 

How fast do you want it?

Answer 3

I remember that there is a solution based on the sum of the digits in the number and other functions
As an example, 3411 is divided by 9, because 3 + 4 + 1 + 1 = 9, the sum of the digits is divided by 9, which also divides the number by 9. The numbers are similar to other rules.