1到100000的因数
将1到100000的因数存起来，要求用尽量快，且用尽量少的空间
首先很容易想到的就是就是将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）
查看11道真题和解析