1到100000的因数

将1到100000的因数存起来，要求用尽量快，且用尽量少的空间

首先很容易想到的就是就是将n个数的因数存进数组里，然后每个数分别用 $O(\sqrt{n})$ ，时间复杂度为 $O(n\sqrt{n})$

不难求出1到100000里面最多的有128个因数，代码如下：

#include <stdio.h>
#include <math.h>

typedef struct
{
	int a[100000][128];
	int num[100000];
}Data;

Data d;

int main()
{
	int i, n, j;
	for (i = 0; i < 100000; i++)
	{
		for (j = 1; j <= sqrt(i + 1); j++)
		{
			if ((i + 1) % j == 0)
			{
				d.a[i][d.num[i]++] = j;
				if (j != (i + 1) / j)
				{
					d.a[i][d.num[i]++] = (i + 1) / j;
				}
			}
		}
	}
	printf("%dk\n", (100000 * 128 + 100000 + 3) * 4 / 1024);
	
	return 0;
}

用了50390k的空间，这可是很大的空间

说到省空间，用数组存起来，不就是对空间的一种浪费吗？比如1只有1这一个因数，而却开了那么大的空间，这时就可以用链表来存起来，代码如下：

#include <stdio.h>
#include <math.h>
#include <malloc.h>

typedef struct Node
{
	struct Node *next;
	int data;
}List;

List *l[100000];

int main()
{
	int i, j, n, sum, num;
	List *p;
	sum = 0;
	for (i = 0; i < 100000; i++)
	{
		for (j = 1; j <= sqrt(i + 1); j++)
		{
			if ((i + 1) % j == 0)
			{
				List *s = (List*)malloc(sizeof(List));
				s->data = j;
				s->next = NULL;
				if (l[i])
				{
					p->next = s;
					p = p->next;
				}
				else
				{
					l[i] = s;
					p = l[i];
				}
				if (j != (i + 1) / j)
				{
					List *s = (List*)malloc(sizeof(List));
					s->data = (i + 1) / j;
					s->next = NULL;
					p->next = s;
					p = p->next;
				}
			}
		}
	}
	
	for (i = 0; i < 100000; i++)
	{
		num = 0;
		if (l[i])
		{
			p = l[i]->next;
			while (p)
			{
				num++;
				l[i]->next = p->next;
				free(p);
				p = l[i]->next;
			}
			num++;
			free(l[i]);
		}
		sum += 2 * num + 1;
	}
	printf("%dk\n", (sum + 4) * 4 / 1024);
	
	return 0;
}

这样一来，虽然时间复杂度还是那样，但就只用了9505k，比之前节省了不少空间，但还是挺大的，还可以进一步减少空间

不难发现一个数的因数与其中的任两个因数的因数有着一定的关系，以100为例

100的因数有1，2，4，5，10，20，25，50，100

而100 = 2 * 50

50的因数又有1，2，5，10，25，50

2 * 50的各个因数，得2，4，10，20，50，100

这两个集合的并集即为100的因数

可能大家在想为什么这样就可以呢，其实道理很简单：

对于n = p * q，p为n大于1且不为本身的最小因数，q分解后的所有因数显然都为n的因数，而p*（q的因数）也肯定是n的因数，这样就快速地找出了所有因数

而且运用指针直接指过去，还省下了不少空间，代码如下：

#include <stdio.h>
#include <math.h>
#include <malloc.h>

typedef struct Node
{
	struct Node *next;
	int data;
}List;

List *l[100000];

int main()
{
	int i, j, n, sum, num;
	List *p, *q;
	sum = 0;
	for (i = 0; i < 100000; i++)
	{
		num = 0;
		for (j = 2; j <= sqrt(i + 1); j++)
		{
			if ((i + 1) % j == 0)
			{
				q = l[(i + 1) / j - 1];
				while (q)
				{
					if ((i + 1) / j % (j * q->data))
					{
						num++;
						List *s = (List*)malloc(sizeof(List));
						s->data = j * q->data;
						s->next = NULL;
						if (l[i])
						{
							p->next = s;
							p = p->next;
						}
						else
						{
							l[i] = s;
							p = l[i];
						}
					}
					q = q->next;
				}
				break;	
			}
		}
		if (j > sqrt(i + 1))
		{
			num++;
			List *s = (List *)malloc(sizeof(List));
			s->data = 1;
			s->next = NULL;
			l[i] = s;
			if (i)
			{
				num++;
				List *s = (List *)malloc(sizeof(List));
				s->data = i + 1;
				s->next = NULL;
				l[i]->next = s;
			}
		}
		else
		{
			p->next = l[(i + 1) / j - 1];
		}
		sum += 2 * num + 1;
	}
	printf("%dk\n", (sum + 5) * 4 / 1000);
	
	return 0;
}

这时只需要3871k的空间，时间复杂度也降低了，不过仍可以继续降低时间复杂度

在上面的做法中，很显然地，我们找的最小的因数其实可以说是最小的质因数，可以利用埃拉托色尼筛选法找出所有素数后，快速找到最小的质因数

#include <stdio.h>
#include <math.h>
#include <malloc.h>

typedef struct Node
{
	struct Node *next;
	int data;
}List;

List *l[100000];
int r[100000];

int main()
{
	int i, j, n, sum, num;
	List *p, *q, *l2, *k;
	for (i = 0; i < 100000; i++)
	{
		r[i] = 1;
	}
	for (i = 2; i <= sqrt(100000); i++)
	{
		for (j = i; i * j <= 100000; j++)
		{
			r[i * j - 1] = 0;
		}
	}
	List *s = (List *)malloc(sizeof(List));
	s->data = 2;
	s->next = NULL;
	l2 = s;
	p = l2;
	sum = 1;
	for (i = 2; i < 100000; i++)
	{
		if (r[i])
		{
			sum++;
			List *s = (List *)malloc(sizeof(List));
			s->data = i + 1;
			s->next = NULL;
			p->next = s;
			p = p->next;
		}
	}
	sum = sum * 2 + 1;
	for (i = 0; i < 100000; i++)
	{
		num = 0;
		k = l2;
		while (k && k->data <= sqrt(i + 1))
		{
			if ((i + 1) % k->data == 0)
			{
				q = l[(i + 1) / k->data - 1];
				while (q)
				{
					if ((i + 1) / k->data % (k->data * q->data))
					{
						num++;
						List *s = (List*)malloc(sizeof(List));
						s->data = k->data * q->data;
						s->next = NULL;
						if (l[i])
						{
							p->next = s;
							p = p->next;
						}
						else
						{
							l[i] = s;
							p = l[i];
						}
					}
					q = q->next;
				}
				break;	
			}
			k = k->next;
		}
		if (k->data > sqrt(i + 1))
		{
			num++;
			List *s = (List *)malloc(sizeof(List));
			s->data = 1;
			s->next = NULL;
			l[i] = s;
			if (i)
			{
				num++;
				List *s = (List *)malloc(sizeof(List));
				s->data = i + 1;
				s->next = NULL;
				l[i]->next = s;
			}
		}
		else
		{
			p->next = l[(i + 1) / k->data - 1];
		}
		sum += 2 * num + 1;
	}
	printf("%dk\n", (sum + 100007) * 4 / 1024);
	
	return 0;
}

这样优化后，时间复杂度约为O(nlgn)，用了7852k的空间
不过空间仍可以减少，只需利用位掩码实现埃拉托色尼筛选法即可大幅度减少空间（所开数组长度为原来的1/8）