求因子个数的问题

shingyuan · 发表于 2011-11-9 11:55:41

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

有这样一个问题：

求一个形如这样的数：$\frac{n(n+1)}{2}$ 的因子个数。

比如 1+2+3 = 6 = 3*(3+1)/2

这个数的因子是： 1,2,3,6总共4个

对于一个一般的形如上面所说的数，如果才能快速计算出其因子的个数呢？

我的计算方法没任何技巧，比较慢：

for(i=1;;i++)
{
k = 0;
for(j=1;j<=i*(i+1)/2;j++)
{
if((i*(i+1)/2)%j==0)
{
k++;
}
if(k>=500)
{
cout << "the number is : " << i*(i+1)/2;
break;
}
}
}

复制代码

我是计算因子个数超过500个的时候，这个数是多少。这个程序对于比较小的数还可以，对于稍微大一点的数，就算不出来了。我是对于<i*(i+1)/2 这样形式的数，一个一个去判断，看看取模是否为零，然后确定其是否为其约数。不过效率貌似太低。

liangbch · 发表于 2011-11-9 13:23:49

32位系统，整数的最大值是max_uint=2^32-1=4294967295
若 n*(n+1)/2<max_uint,则n的最大值是92681，n的平方根的最大值304.

对此题目，可使用下面的步骤来做
1. 先用筛法求出304以内的所有素数。
2. 然后对m=n*(n+1)/2 分解素因数。
3. 假定m=p1^e1 * p2^e2 * ... * pn^e5,则这个m的所有因数个数是(e1+1)*(e2+1)*... *(en+1)

by the way, 此题目的复杂度是相当的低。

楼下将给出代码

liangbch · 发表于 2011-11-9 15:27:15

代码完成，可在1秒内检查完所有的数。最多有1024个因子
第一个含有1024个因子的数是73359, 73359*(73359+1)/2 有 1024 个因子

// URL: http://bbs.emath.ac.cn/redirect.php?tid=3786&goto=lastpost#lastpost
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <memory.h>
typedef unsigned long DWORD;
typedef unsigned char BYTE;
// 一定范围内质数的个数
// 10 4
// 100 25
// 1,000 168
// 10,000 1,229
// 100,000 9,592
// 1,000,000 78,498
// 10,000,000 664,579
// 100,000,000 5,761,455
// 1,000,000,000 50,847,534
// 10,000,000,000 455,052,511
// 100,000,000,000 4,118,054,813
// 1,000,000,000,000 37,607,912,018
// 10,000,000,000,000 346,065,536,839
// 100,000,000,000,000 3,204,941,750,802
// 1,000,000,000,000,000 29,844,570,422,669
// 10,000,000,000,000,000 279,238,341,033,925
// 100,000,000,000,000,000 2,623,557,157,654,233
// 1,000,000,000,000,000,000 24,739,954,287,740,860
// 估计x 范围内的质数的个数，欧拉公式 pi(x)=x /( ln(x));
// 经过测试，
// 在1-1百万之间，相邻2个质数的最大差为114,这两个质数分别为492113,492227
// 在1-1千万之间，相邻2个质数的最大差为154,这两个质数分别为4652353,4652507
// 在1-3千万之间，相邻2个质数的最大差为210,这两个质数分别为20831323,20831533
// 在1-1亿之间，相邻2个质数的最大差为220,这两个质数分别为47326693,47326913
#define MAX_PRIME 302
struct FAC_ARR_ST
{
int fc;
struct
{
DWORD p;
int e;
}arr[10]; //2^32以内的数最大9个素因子
};
struct FAC_ARR_ST g_facTab;
void clear_facTab()
{
g_facTab.fc=0;
memset(g_facTab.arr,0,sizeof(g_facTab.arr));
}
void add_to_facTab(DWORD p)
{
int i;
int bfind=0;
for (i=0;i<g_facTab.fc;i++)
{
if ( g_facTab.arr[ i ].p==p)
{
g_facTab.arr[ i ].e++;
bfind=1;
break;
}
}
if ( !bfind )
{
g_facTab.arr[g_facTab.fc].p=p;
g_facTab.arr[g_facTab.fc].e=1;
g_facTab.fc++;
}
}
//**********************************************
// n 不能大于L2 cache，否则效能很低
DWORD Sift32(DWORD n,DWORD *primeTab)
// 对0到n 之间(不包括n)的数进行筛选，返回质数的个数
//**********************************************
{
BYTE *pBuff= new BYTE[n];
if (pBuff==NULL)
return 0;
DWORD i,sqrt_n,p;
DWORD pn;
//----------------------------
sqrt_n=(DWORD)(sqrt(n)+1);
while (sqrt_n * sqrt_n >=n)
sqrt_n--;
memset(pBuff,1,n*sizeof(BYTE));
*pBuff=0;
*(pBuff+1)=0; //1不是质数
*(pBuff+2)=1; //2是质数
for ( i=4;i<n;i+=2) //筛去2的倍数，不包括2
*(pBuff+i)=0;
for (i=3;i<=sqrt_n;) //i 是质数
{
for (p=i*i;p<n; p+=2*i)
*(pBuff+p)=0; //筛去i 的奇数倍
i+=2;
while ( *(pBuff+i)==0 )
i++; //前进到下一个质数
}
pn=0; //素数个数
if ( primeTab==NULL)
{
for (i=2;i<n;i++)
{
if (pBuff[ i ])
pn++;
}
}
else
{
for (i=2;i<n;i++)
{
if (pBuff[ i ])
{
primeTab[pn++]=i;
}
}
}
delete[] pBuff;
return pn;
}
void check_all(DWORD max_n)
{
DWORD *primeTab=NULL;
DWORD primeCount;
DWORD i,j,k;
int f_c; //总的因子数
int max_fc;
//创建一个素数表
primeCount=Sift32(MAX_PRIME,NULL); //得到MAX_PRIME以内的素数个数
primeTab=(DWORD *) malloc(sizeof(DWORD)* (primeCount+1));
Sift32(MAX_PRIME,primeTab);
primeTab[primeCount]=2147483647; //设置一个栅栏
max_fc=0;
//-----------------------------------------
for (i=2;i<=max_n;i++)
{
DWORD na[2];
if (i & 1) //i是奇数
{ na[0]=i; na[1]=(i+1)/2;}
else
{ na[0]=i/2; na[1]=i+1; }
clear_facTab(); // n*(n+1)/2的素因子数表初始化为空
for (j=0;j<2;j++)
{
DWORD n=na[j];
DWORD r;
// primeTab[primeCount]=2147483647，保证循环能够终止
r=n;
for (k=0; primeTab[k] * primeTab[k] <= n && r>1; )
{
DWORD prime=primeTab[k];
if ( n % prime==0)
{
add_to_facTab(primeTab[k]); //增加素因子到素因子表 g_facTab
r/=primeTab[k];
}
k++;
}
if (r>1)
add_to_facTab(r);
}
f_c=1;
for (j=0;j<g_facTab.fc;j++)
f_c *= (g_facTab.arr[j].e +1);
//printf("%u*(%u+1)/2 with %u factor\n",i,i,f_c);
if (f_c >max_fc)
{
printf("%u*(%u+1)/2 with %u factor\n",i,i,f_c);
max_fc=f_c;
}
}
free(primeTab);
}
int main(int argc, char* argv[])
{
check_all(92681);
return 0;
}

复制代码

wayne · 发表于 2011-11-9 15:43:01

有才

shingyuan · 发表于 2011-11-9 16:46:18

首先感谢liangbch，里面提到的算法很有用：

m=p1^e1 * p2^e2 * ... * pn^e5,则这个m的所有因数个数是(e1+1)*(e2+1)*... *(en+1)

我用这个也算了下，的确速度很快。我是对每个数，统计下其素因子个数，然后按照公式算。

#include <iostream>
using namespace std;
void main()
{
int a[200],n,i,j,k,ans,answer,l,end;
for(n=0;n<200;n++)
{
a[n] = 0;
}
for(i=1;;i++)
{
k = 0;
answer = i*(i+1)/2;
ans = i*(i+1)/2;
for(j=2;j<=ans;j++)
{
if(ans%j == 0)
{
while(ans%j==0)
{
a[k]++;
ans = ans / j;
}
k++;
}
}
end = 1;
for(l=0;l<k;l++)
{
end = (a[l]+1)*end;
}
if(end >= 500)
{
cout << "end is :"<< end << endl;
cout << "answer is : " << answer << endl;
break;
}
for(n=0;n<200;n++)
{
a[n] = 0;
}
}
}

复制代码

liangbch · 发表于 2011-11-9 17:24:59

你这个求m的素因子的代码还是有待改进，在最坏情况下，求m的所有素因子的复杂度是sqrt(m)/ln(sqrt(m)),不必从2逐一试除到m

G-Spider · 发表于 2011-11-9 17:51:33

好厉害。

liangbch · 发表于 2011-11-9 20:13:21

看了一下楼主的代码，并将int 型变量改为unsigned long后，发现楼主的代码也只能检查到65535，当i>65535, 5楼第12行代码会发生整数溢出。

answer = i*(i+1)/2;

我的代码可检查到 92681。

对楼主的代码做了如下修改，并增加了时间花费检测，发现，当检测到65535时，我的程序用时为21.6毫秒，楼主的程序为2081毫秒。
1.修改变量定义，将int型改为unsigned long,增加数据范围。
2.屏蔽5楼的第36-38行。

36.                      // cout << "end is :"<< end << endl;
37.                      //cout << "answer is : " << answer << endl;
38.                      // break;

3. 将 “for(i=1;;i++)” 改为 “for(i=1;i<65536;i++)”

我的代码有少许修改，
1. 将3楼第210行改为“check_all(65535);“
2.在3楼183行后增加 "if ( primeTab[k]>r) break",如果不修改此处，用时为22.1毫秒

gxqcn · 发表于 2011-11-9 20:23:18

3# 代码价值信息量很大！

需要花点时间好好咀嚼。

liangbch · 发表于 2011-11-9 20:27:23

楼上过奖了。关于筛法求素数和分解质因数，楼上亦可称为专家，对楼上来说，我的代码很很稀松平常，没什么值得学习的，不过对于初学者，应该具有参考价值。

账号		自动登录	找回密码
密码			欢迎注册

[求助] 求因子个数的问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。