HDOJ1215

例题：输入一个数N，输出所有小于等于N的素数
基本思想：素数的倍数一定不是素数
实现方法：用一个长度为N+1的数组保存信息（0表示素数，1表示非素数），先假设所有的数都是素数（初始化为0），从第一个素数2开始，把2的倍数都标记为非素数（置为1），一直到大于N；然后进行下一趟，找到2后面的下一个素数3，进行同样的处理，直到最后，数组中依然为0的数即为素数。说明：整数1特殊处理即可。

#include<iostream>
#include<math.h>
using namespace std;
int a[100001];
int main()
{
	int i, n,j;
	while (cin >> n)
	{
		for(i=2;i<=n;i++)
			if (a[i] == 0) {
				for (j = i + i; j <= n; j += i)
					a[j] = 1;
			}
		cout<<"2";
		for (i = 3; i < n; i++)
			if (a[i] == 0)cout <<i;
		cout <<endl;
	}
}

和例题相似的处理方式，先定义一个a[t]来保存t对应的所有因子之和
对于一个i，它一定是所有i的倍数的因子，因此将a[ix]都加上i(ix表示i的所有倍数)

#include<iostream>
#define MAXN 500005
int a[MAXN];
using namespace std;
int main()
{
	int i, j;
	for( i=1;i<=MAXN/2;i++)
		for (j = i + i; j <= MAXN; j+=i)
			a[j]+=i;
	int n;
	cin >> n;
	while (n--)
	{
		int t;
		cin >> t;
		cout << a[t]<< endl;
	}
}