这个程序的功能是采用高效的算法，将n以内的的所有自然数分解质因数，并存储起来，最后输出其分解式。
1.自然数的分解
根据算术基本定理,一个大于1的自然数能够唯一分解成几个素数乘积的形式。
如\(120=2 \times 2 \times 2 \times 3 \times 5\)。我们这里，将自然数的分解式写成\(n=(p_1^{e_1}) \times (p_2^{e_2}) \times \cdots \times (p_m^{e_m})\)的形式，这里\(p_1,p_2,p_m\)表示素数，\(p_1^{e_1}\), \(p_2^{e_2}\)表示素数的方幂。
如\(120=(2^3)\times(3^1)\times(5^1)\)
2. 非重复素因子的个数
若一个自然数表示为几个素数乘积的形式，则去掉重复因子后，其因子的个数叫做这个自然数的非重复素因子的个数。如120含有3个非重复素因子，他们分别是2,3,5。容易看出，不同的自然数，其非重复素因子个数可能不同的，如27仅有1个非重复素因子3，而210含有2,3,5,7四个非重复素因子。\(2^{32}\)以内的所有整数中，其非重复素因子个数最多不超过9个，这个因为前10个素数的乘积\(2\times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29=6,469,693,230>2^{32}\)
3.自然数分解式的表示
若 \(n=(p_1^{e_1}) \times (p_2^{e_2}) \times \cdots \times (p_m^{e_m})\)，我们说这个自然数的分解式包含m项，每项包含2个成员,素因子p和其指数e。自然数的分解式可顺序存储，也可采用链式存储，前者其分解式的所有项的地址是相邻的，各项顺序存放。后者其分解式的每项的地址是不相邻的，使用单链表来存储。链式存需要额外的空间来存储指针，不但内存占用率高，且运行效率也低，故此文中的程序采用顺序存储方式。
4.算法
4.1 首先，函数sift采用与筛法求素数类似的方法，求出n以内所有的素数，并统计出每个合数的非重复素因子的个数。
4.2 接着，程序算出所有n以内的所有自然数分解式的项数的之和，分配内存来存储其分解式，并确定每个自然数的分解式的的地址。方法是：若c_arr[i]表示自然数i的素因子的个数，a_arr[i]表示自然数i的的分解式的存储地址，则自然数i+1的的分解式的地址a_arr[i+1]=a_arr[i]+c_arr[i]
4.3 然后，函数buildfactorTable将n以内的所有自然数分解，并存储其分解式。
4.4 最后，函数print_factor输出每个自然数的分解式。
5.复杂度分析
5.1 空间复杂度
函数batchDecompose 在运行过程中动态分配了3个数组，buff,addrtable和factorTable，前两个数组大小分别为n+1和n+2。最后一个数组的大小取决于n以内每个数的分解式的项数的和。n以内平均每个数的非重复素因子的个数约为log(log(n))，故factorTable的大小约为n*log(log(n))，故总的空间复杂度为o(n*log(log(n)))
5.2 时间复杂度
函数sift的时间复杂度度亦为o(n*log(log(n))),计算addrTable的时间复杂度为o(n),函数buildfactorTable的时间复杂度稍大于o(n*log(log(n))),故总的时间复杂度稍大于o(n*log(log(n)))
下面是C语言源代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
#include <stdlib.h> #include <stdio.h> #include <string.h> typedef unsigned char BYTE; typedef unsigned long DWORD; typedef struct _pe_pair { DWORD p; //p是素数 DWORD e; //e是指数 }PE_PAIR; //筛出n以内(包括n）的所有素数，并统计n以内所有自然数的非重复素因子的个数 //当函数完成后，若pBuff[i]==0, 表明i是素数， //若pBuff[i]>0, 表明i是合数，且i的非重复素因子的个数是pBuff[i] void sift(BYTE *pBuff,DWORD n) { DWORD p,m; memset(pBuff,0,sizeof(BYTE)*(n+1)); p=2; while (p<=n) { for (m=p*2;m<=n;m+=p) //p素数，m是p的倍数，将p的倍数（不包括p）的非重复素因子的个数增加1 pBuff[m]++; p++; //调到下一个数 while ( pBuff[p] && p<=n) //略过合数 p++; } } // 函数 print_factor输出n以内所有自然数的分解式 // addrTable是地址表，addrTable[i]表示自然数i的因子表的地址 // addrTable[i+1]-addrTable[i]表示自然数i的分解式的项数，addrTable包含n+2个元素，前3个元素不使用 // factorTable[addrTable[i]] 为自然数i的分解式的第一项 void print_expression(DWORD *addrTable,PE_PAIR *factorTable,DWORD n) { DWORD i,j,c; PE_PAIR *tab; for (i=2;i<=n;i++) { c=addrTable[i+1]-addrTable[i]; tab=factorTable+addrTable[i]; printf("%u=",i); for(j=0;j<c;j++) { if (j>0) printf("*"); printf("(%u^%u)",tab[j].p,tab[j].e); } printf("\n"); } } /*函数buildTable对n以内的自然数进行分解，并将每个自然数的分解式存储到factorTable 输入参数 n,pBuff,addrTable 输出参数 factorTable */ void buildfactorTable(DWORD n,BYTE *pBuff, DWORD *addrTable,PE_PAIR *factorTable) { DWORD i,p,m,t; PE_PAIR item; //----------------------------------------------------- p=2; while (p<=n) { item.p=p; item.e=1; factorTable[addrTable[p]]=item; addrTable[p]++; for (m=p*2;m<=n;m+=p) //m为p的倍数 { //m是p的倍数，故p一定整除m，故素因子p的指数至少为1 item.p=p; item.e=1; // m可能含有多个素因子p，如120含有3个因子2，下面的代码求出素因子p的指数 t=m/p; while (t%p==0) {t/=p; item.e++; } factorTable[addrTable[m]]=item; addrTable[m]++; } p++; while ( pBuff[p]>0 && p<=n) p++; //略过合数，使得p总是素数 } //当完成上面的代码，addrTable[i]的值实际上为自然数i+1的因子表的首地址 //故需要恢复addrTable为原始值 for (i=n;i>=2;i--) addrTable[i+1]=addrTable[i]; addrTable[2]=0; } //函数batchDecompose批量分解n以内所有自然数的，并打印其分解式 void batchDecompose(DWORD n) { BYTE *buff=NULL; //用来得到n以内的所有素数，和所有合数的素因子的个数 DWORD *addrTable=NULL; //地址表，addrTable[i]表示自然数i的分解式在factorTable中的偏移地址 PE_PAIR *factorTable=NULL; DWORD i,c,total; buff =(BYTE *)malloc(sizeof(BYTE)*(n+1)); addrTable =(DWORD *)malloc(sizeof(DWORD)*(n+2)); if (buff==NULL || addrTable==NULL) { printf("Alloc memory failed\n"); goto free_memory;} sift(buff,n); addrTable[0]=addrTable[1]=addrTable[2]=0; for (total=0,i=2;i<=n;i++) { c= (buff[i]==0 ? 1: buff[i]); //c为自然数i的素因子的个数 total += c; addrTable[i+1]=addrTable[i]+c; //计算自然数i+1的分解式在factorTable中的偏移地址 } factorTable=(PE_PAIR *)malloc(sizeof(PE_PAIR)*total); if (factorTable==NULL) { printf("Alloc memory failed\n"); goto free_memory; } buildfactorTable(n,buff,addrTable,factorTable); //将n以内的自然数的分解式存储到factorTable print_expression(addrTable,factorTable,n); //打印将n以内所有自然数的分解式 free_memory: if (buff!=NULL) {free(buff);buff=NULL;} if (addrTable!=NULL) {free(addrTable);addrTable=NULL;} if (factorTable!=NULL) {free(factorTable);factorTable=NULL;} } int main(int argc, char* argv[]) { batchDecompose(100); return 0; } |