如何快速简便的找出一个数的所有因子

奔跑吧，参考：

#include <math.h>
#include <stdio.h>
int sum_factor(int n)
{
	int i, sum;
	sum = 1;
	for (i = 2; i <= n / 2; i++)
	{
		if (0 == n % i) sum += i;
	}
	return sum;
}
int count(int start, int end, int badness)
{
	int i, gap, sumf, res;
	sumf = res = 0;
	for (i = start; i <= end; i++)
	{
		sumf = sum_factor(i);
		if (sumf >= i) gap = sumf - i;
		else gap = i - sumf;
		if (-badness <= gap && gap <= badness) res++;
	}
	return res;
}
int main() 
{
	int i = 1;
	int start, end, badness;
	while (scanf("%d%d%d", &start, &end, &badness))
	{
		getchar();
		if (0 == start && 0 == end && 0 == badness) break;
		printf("Test %d: %d\n", i, count(start, end, badness));
		i++;
	}
	return 0;
}

应该注意到 Divisor Function(1到n中所有能整除n的整数之和)为积性函数，即对于两互质的整数p,q有f(pq) = f(p) f(q)，应尽可能利用这一点，缓存f(n)的值以备将来计算f(kn)使用

代码仅供参考：

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 1000000

typedef long long LL;

LL table[MAX_N] = {0, 1};

LL sod(int n)
{
	if (table[n] != 0) return table[n];
	int p, q, c;
	for (p = 2; p < n / 2; p++)
	{
		if ( n % p == 0 ) break;
	}
	if (n % p != 0)
	{
		table[n] = 1 + n;
		return table[n];
	}
	else
	{
		int pn = p;
		LL sum = 1 + p;
		while ((q = n / pn) % p == 0)
		{
			pn *= p;
			sum += pn;
		}
		table[pn] = sum;
		table[n] = table[pn] * sod(q);
		return table[n];
	}
}

LL badness_of(int n)
{
	LL ret = sod(n) - 2 * n;
	if (ret < 0) ret = -ret;
	return ret;
}

int main(void)
{
	int start, end, badness, n = 1;
	while(scanf("%d%d%d", &start, &end, &badness) == 3)
	{
		if ((start == 0) && (end == 0) && (badness == 0))
		{
			break;
		}
		int count = 0, i;
		for (i = start; i <= end; i++)
		{
			count += badness_of(i) <= badness;
		}
		printf("Test %d: %d\n", n++, count);
	}
	return 0;
}

#include<stdio.h>
#include<time.h>

unsigned int getbadness(unsigned int n)
{
	unsigned int prime_divisors[7][2]={0};	// 保存质因数及其个数,prime_divisors[i][0]为质因数,prime_divisors[i][1]为其个数
	unsigned int prime_divisors_length=0;	// ps的有效长度
	unsigned int i;
	unsigned int divisors_num=1;			// 用于计算因数个数(包括n自身)
	unsigned int sum=0;						// 用于计算因数的和
	unsigned int n_bak=n;

	// 以下为试除法求n的质因数分解
	// 试除 2
	if(!(n&1))
	{
		prime_divisors[prime_divisors_length][0]=2;
		while(!(n&1))
		{
			++prime_divisors[prime_divisors_length][1];
			n>>=1;
		}
		divisors_num*=prime_divisors[prime_divisors_length][1]+1;
		++prime_divisors_length;
	}
	// 试除 3
	if(!(n%3))
	{
		prime_divisors[prime_divisors_length][0]=3;
		while(!(n%3))
		{
			++prime_divisors[prime_divisors_length][1];
			n/=3;
		}
		divisors_num*=prime_divisors[prime_divisors_length][1]+1;
		++prime_divisors_length;
	}
	for(i=1;n>1;++i)
	{
		if((6*i-1)*(6*i-1)>n)
		{
			prime_divisors[prime_divisors_length][0]=n;
			prime_divisors[prime_divisors_length++][1]=1;
			divisors_num<<=1;
			break;
		}
		// 试除 6i-1
		if(!(n%(6*i-1)))
		{
			prime_divisors[prime_divisors_length][0]=6*i-1;
			while(!(n%prime_divisors[prime_divisors_length][0]))
			{
				++prime_divisors[prime_divisors_length][1];
				n/=prime_divisors[prime_divisors_length][0];
			}
			divisors_num*=prime_divisors[prime_divisors_length][1]+1;
			++prime_divisors_length;
		}
		// 试除 6i+1
		if(!(n%(6*i+1)))
		{
			prime_divisors[prime_divisors_length][0]=6*i+1;
			while(!(n%prime_divisors[prime_divisors_length][0]))
			{
				++prime_divisors[prime_divisors_length][1];
				n/=prime_divisors[prime_divisors_length][0];
			}
			divisors_num*=prime_divisors[prime_divisors_length][1]+1;
			++prime_divisors_length;
		}
	}

	// 以下为求除n自身以外的因数的和
	for(i=0;i<divisors_num-1;++i)
	{
		unsigned int divisor=1,j,ii=i,k;
		for(j=0;ii;ii/=prime_divisors[j++][1]+1)
		{
			k=ii%(prime_divisors[j][1]+1);
			while(k--)divisor*=prime_divisors[j][0];
		}
		sum+=divisor;
	}

	// 返回因数和与n的差的绝对值
	if(sum>n_bak)return sum-n_bak;
	else return n_bak-sum;
}

int main()
{
	unsigned int i;
	clock_t c=clock();
	for(i=2;i<1000000;++i)
		getbadness(i);
	printf("time:%lfs\n",(double)(clock()-c)/CLOCKS_PER_SEC);
	return 0;
}

时间 1.086763s 可以吗

我用最原始的方法做是超时的

查表法