特别鸣谢飞飞提醒，生成素数表效率一下提高了40%之多!
namespace
primeNS
{
/**/
/*
解决：素数表
*算法：筛法
*输入：范围MaxN
*输出：素数个数pp, 素数表[p[0],p[pp])
*备注：效率:1千万时，sicily-0.59 ZOJ-0.85 (朴素版sicily1.00)
*/
const
int
MaxN
=
10000000
;
//
查找[2,maxN]范围的素数
const
int
Len
=
MaxN
/
2
+
1
;
int
p[Len]
=
{
2
}
,pp
=
1
;
void
init()
{
int
i,j,cur;
for
(i
=
1
; ;
++
i)
{
if
(
!
p[i])
{
p[pp
++
]
=
cur
=
i
*
2
+
1
;
//
找到一个素数
for
(j
=
2
*
i
*
(i
+
1
); j
<
Len; j
+=
cur)
p[j]
=
1
;
if
(j
==
2
*
i
*
(i
+
1
))
//
筛完，可照抄
break
;
}
}
for
(
++
i;i
<
Len;
++
i)
//
照抄
if
(
!
p[i])
p[pp
++
]
=
i
*
2
+
1
;
}
/**/
/**/
/**/
/*
解决：质因数分解
*算法：顺搜，逐个测试
*输入：待分解数num, init()的输出
*输出：质因数个数dp, 质因数表d[0dp-1]，指数表e[0dp-1];
*备注：若num>=MaxN^2,可能会将所有大于MaxN的质因数之积看作一质因数
*/
int
d[Len],e[Len],dp;
void
factorization(
int
num)
{
int
i,cnt,div;
dp
=
0
;
for
(i
=
0
;i
<
pp;i
++
)
{
if
(num
%
p[i]
==
0
)
{
d[dp]
=
p[i];
div
=
p[i]
*
p[i]; cnt
=
1
;
while
(num
%
div
==
0
)
{
div
*=
p[i];
++
cnt;
}
e[dp
++
]
=
cnt;
div
/=
p[i];
if
((num
/=
div)
==
1
)
break
;
}
}
if
(num
!=
1
)
{
d[dp]
=
num; e[dp
++
]
=
1
;
}
}
}
using
namespace
primeNS;
#include
<
cstdio
>
int
main()
{
init();
factorization(
293910
);
int
i;
for
(i
=
0
;i
<
dp;
++
i)
{
printf(
"
+%d^%d
"
,d[i],e[i]);
}
printf(
"
\n
"
);
return
0
;
}
posted on 2006-07-11 00:24
踏雪赤兔 阅读(1394)
评论(0) 编辑 收藏 引用 所属分类:
零件仓库