批量分解素因数(二)

本文中的程序使用压缩的格式存储M以内(包含M)的所有奇数的分解式。

和前一个的程序不同,这个程序侧重于使用尽可能少的内存空间来保存M以内的所有奇数的分解式.
本文中的程序可计算65759以内的所有奇数的因子表,其因子表占用的内存空间不到200KB,32881*2+65535*2=196,832字节.
和上一篇文章一样,M以内的奇数的分解式需要使用两个表格来存储,地址表addrTable和因子表factorTable.
地址表使用WORD类型,addrTable[i]==0,表示(i*2+3)为素数,否则addrTable[i]表示(i*2+3)分解式的第一项的地址.
factorTable[0]不使用,factorTable的最后一项也不使用,故其存储的因子表的总数不能超过65534.
分解式的每一项,仅用一个WORD类型变量来存储,即每一项仅需2个字节。
当奇数x=2*i+3是素数时,其分解式无需存储在factorTable,这时,置addrTable[i]==0。
当奇数x=2*i+3是合数时,且其素因子p的指数为1时,在这种情况下,置bit15=1,用bit0-bit14存储p,这里p的最大取值是32767,故M的最大取值范围不超过3*32767=98,301.
当奇数x=2*i+3是合数时,且其素因子p的指数大于1,在这种情况下,置bit15=0,用bit0-bit8存储p,用bit9-bit14存储指数e,这里p的最大取值不超过511,故M的最大取值范围不超过511*511=261,121.
更多的细节,请参阅源代码。

下面给出源代码

发表评论

邮箱地址不会被公开。 必填项已用*标注