Efficiently testing if sigma(n) = m I'm trying to write a function that efficiently solves this problem:
Given positive integers m and n, determine whether $\sigma(n)=m$.
Of course I'm looking for a faster technique than "factor n, determine sigma(n), and check if the two are equal" or I wouldn't have posted here.  My basic idea is finding small factors of n (or their absence) and short-circuiting if no factorization of the remaining part would give m.
Other tests, like requiring that $n$ be a square or twice a square if $m$ is odd, come to mind.
Any other ideas, or thoughts on how to actually implement this?  If $m/n$ is very large it can be disqualified by comparing to a list of superabundant numbers and their abundancies, but if it is within the possible range I'd need to find some equivalent way to disqualify numbers that have no factors below some limit L to which I have tested, and it's not clear how to do this.
(Of course if I'm fortunate enough to find a component $p^a\parallel n$ with $\sigma(p^a)\nmid m$ I'm done, but too many numbers have no small factors to rely on finding this in all cases.)
 A: It has been a while since I played with this when searching for amicable numbers, but here are a few suggestions.
EDIT:  Seeing the other answer, it appears that I should mention that $\sigma$ is multiplicative, i.e. if $n=\prod_i p_i^{e_i}$ then $\sigma(n) = \prod_i (p_i^{e_i+1}-1)/(p-1)$, this is necessary for the following.
Assuming that you have a table of primes run through the primes until you find a factor of $n$ and act accordingly.  You only need primes up to around $n^{1/3}$.


*

*While you run through the small 
    prime factors of n, say you find
    that    $p^e | n$ check that
    $\sigma(p^e) |    m$.  (It is
    probably best to divide    it out
    and check that $\sigma(n/p^e)    =
        m/\sigma(p^e)$ (obviously not bothering with primes smaller than $p$ going forward).  This tends to short
    circuit the computation very quickly.

*Obviously short circuit when $n>m$. This is why dividing out the factors of $p^e$ and $\sigma(p^e)$  is useful.  In my experience steps 1 and 2 are the most powerful.   Also test if $n+1=m$ and $n$ prime.

*If you are at a large enough p that
you know that there can be only two
prime factors, solve the quadratic resulting from $n = pq$, $m=(p+1)(q+1)$, so $n-m+1=p+q$ so p and q are roots of  $x^2 + (m-n-1) x + n$ (check my algebra).
(you also need to check if $n = p^2$
and $m = p^2+p+1$, but this is easy as $p=m-n-1$.

*Very occasionally (say whenever $p$ passes $2^k$ for $k>10$)  check if $\sigma(n)$ must be smaller than $m$ by assuming that all the remaining factors of $n$ are distinct factors of size $p$. This gets fiddly, and I forget the details.  The idea comes from H. J. J. TeRiele's 1986 amicable pair paper in Math Comp.  Essentially if $n=p^k q$ then $m < (p+1)^k (q+1)$ with $p<q<p^2$ ($q$ not necessarily integer)[*]

*If you have dealt with the even prime, and you should do that first, then it is worth handling the case of odd $m$ separately (this is another reason to divide out $\sigma(p^e)$ as you find them.  As you divide out small primes the powers of 2 in $m$ disappear fairly quickly. 

*One more thing (a combination of 2 and 3) if $m<n+n^{2/3}+n^{1/3}+1$ then $n$ must have one or two  prime factors, and you can apply 3.


[*] This is not too fiddly after all.  If $p$ is a prime factor of $n$ the most it can contribute to $\sigma(n)/n$ is $(p+1)/p$, so if we want a bound on maximum possible value of $\sigma(n)$ given that $n$ has no prime factor smaller than $p$, and $n$ has $k$ prime factors, we can use the maximum of $\prod_i (p_i+1)$ constrained by $\prod_i p_i = n$ and $p_i>p$.  This is a Lagrange multiplier problem and it is easy to see that it is maximized on the boundary and the maximum value is $(p+1)^{k-1} (q+1)$, and if we maximize this with respect to $k$ we see that we must choose $k$ to be as large as possible such that $q>p$.
A: You could try a sieve. The simplest one that comes to mind is creating a list from 1 to some number n where initially each element in the list has the value 1; loop through the list continually adding the current number you're at to its multiples until you hit the end of the list. Here is some code (in C++): 
int n = 1000000; // limit of the sieve
vector <int> sigma(n+1,1);
for(int i = 2;i <= n; i++)
    for(int j = i;j <= n;j += i)
        sigma[j] += i;

A: Bach, Miller and Shallit showed that given $\sigma(n)$ and n you can factor n in random polynomial time, which can be used for what you want. The paper is Sums of Divisors, Perfect Numbers and Factoring. 
