Divisor Function

Prime Factorization and Divisor Function σ_x(n)

σ_x(n) is defined as the sum of x^th powers of the distinct positive divisors of n. The function can be expressed as:

Here, r = ω(n), which is the number of distinct positive prime factors of n. p_i for i = 1 to r, are the prime factors and a_i is the maximum power of p_iby which n is divisible.

Clearly, this function can be used for various problems, for example, when x = 0, it simply means the number of distinct positive divisors of n, if x = 1, it is the sum of distinct positive divisors of n, for x = 2, its the sum of squares of positive divisors of n and so on.

For programming contest practice, there are a few problems that requires sum of divisors, or number of divisors, which can be calculated by simply calculating the prime factors with their count, and then evaluating the function shown above with appropriate value on x. Also, the form of function definition can be changed when you set a value for x. After putting x = 0, we get this:

So this is easy, you just need to find frequency of each prime, and then multiply each (a_i + 1) for all primes, you get the number of divisors of n.

For sum of divisor, the idea is similar, here x = 1. The following code shows how to find sum of distinct positive divisors of n:

 #include <cstdio> #include <cmath> using namespace std;  #define sq(x) ((x)*(x)) #define i64 unsigned long long #define MAX 784 #define LMT 28  unsigned flag[MAX/64]; unsigned primes[5761460], total;  #define chkC(n) (flag[n>>6]&(1<<((n>>1)&31))) #define setC(n) (flag[n>>6]|=(1<<((n>>1)&31)))  /* Regular sieve of eratosthenes, bitwise implementation */ void sieve() {     unsigned i, j, k;     flag[0]|=0;     for(i=3;i<LMT;i+=2)         if(!chkC(i))             for(j=i*i,k=i<<1;j<MAX;j+=k)                 setC(j);     primes[(j=0)++] = 2;     for(i=3;i<MAX;i+=2)         if(!chkC(i))             primes[j++] = i;     total = j; }  /* finds n^p in log(p) time */ i64 power(unsigned n, unsigned p) {     i64 x=1, y=n;     while(p > 0)     {         if(p&1) x *= y;         y *= y;         p >>= 1;     }     return x; }  /* calculates the sigma(1) function, we don't need to find prime frequencies. */ inline void update(i64 &sigma1, i64 n, unsigned p) {     if(p==1) sigma1 *= (n+1);     else sigma1 *= ((power(n,p+1)-1)/(n-1)); }  /* Factorization function, we do not need to store the primes here, instead, whenever a prime is found, you update corresponding prime and frequency with sigma 1 */ void factor(i64 n, i64 &sigma1) {     unsigned i, v;     i64 t;     for(i=0, t=primes[i]; i<total && t*t <= n; t = primes[++i])     {         if(n % t == 0)         {             v = 0;             while(n % t == 0)             {                 v++;                 n /= t;             }             update(sigma1, primes[i], v);         }     }     if(n>1) update(sigma1, n, 1); }  /* Our beloved main function */ int main() {     int t, x;     i64 n, sigma1;     sieve();     scanf("%d", &t);     for(x=1; x<=t; x++)     {         scanf("%llu", &n);         factor(n, sigma1);         printf("%llu\n",sigma1);     }     return 0; } 

We just need the values of σ, so here we will not store the prime factors. Some similar problem would be to find the number of odd divisors of n, or testing if a number is square free, i.e. no perfect square divides n, going to leave these as an exercise for readers.

A closer look to σ function from wikipedia.

Pollard's Rho in Java

This is a Pollard's Rho implementation in java. Not very fast, but works for uva online judge. The reason behind using java is the default support of the BigInteger class.

import java.math.BigInteger;
import java.security.SecureRandom;
import java.io.*;
import java.util.*;

public class PollardRho {

    private final static BigInteger ZERO = new BigInteger("0");
    private final static BigInteger ONE  = new BigInteger("1");
    private final static BigInteger TWO  = new BigInteger("2");
    private final static SecureRandom random = new SecureRandom();

    static Vector<BigInteger> v = new Vector<BigInteger>();

    public static BigInteger rho(BigInteger N) {

        BigInteger divisor;
        BigInteger c  = new BigInteger(N.bitLength(), random);
        BigInteger x  = new BigInteger(N.bitLength(), random);
        BigInteger xx = x;

        if (N.mod(TWO).compareTo(ZERO) == 0) return TWO;

        do {
            x  =  x.multiply(x).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            xx = xx.multiply(xx).mod(N).add(c).mod(N);
            divisor = x.subtract(xx).gcd(N);
        } while((divisor.compareTo(ONE)) == 0);

        return divisor;
    }

    public static void factor(BigInteger N) {

        if (N.compareTo(ONE) == 0) return;

        if (N.isProbablePrime(20)) {
            v.add(N);
            return;
        }

        BigInteger divisor = rho(N);
        factor(divisor);
        factor(N.divide(divisor));
    }

    public static void main(String[] args) throws Exception {

        String string = "";
        InputStreamReader input = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(input);

        while(null != (string = reader.readLine())) {
            BigInteger N = new BigInteger(string);
            v.clear();
            factor(N);
            Collections.sort(v);
            for(int i = 0; i < v.size(); i++) System.out.println(v.get(i));
            System.out.println();
        }
    }
}

I have seen this piece of code years ago somewhere in the internet, but can't remember exactly where. So, I will be glad if anyone can comment/mail me the original source. However, for spoj, I need to write a much much better version of this in C++ :( Exam sucks life...