请教一个问题

gracias · 发表于 2012-1-8 01:18:32

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

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

×

整数都可以分解成$N = p_1^{i_1} * p_2^ {i_2} * ...*p_n^{i_n}$如果不考虑$p_1,p_2,...,p_n$具体是多少而只考虑其最后分解结果中不同素因子的个数及其幂. 例如用$[i_1,i_2,...,i_n]$表示一个数含有$n$个不同的素因子,其幂依次为$i_1,i_2,...,i_n$ 问题是能不能快速有效的求出所有某个范围内的数中有多少个数的分解形式为$[i_1,i_2,...,i_n]$? $N=p_1^{i_1}p_2^{i_2}...p_n^{i_n}$

wayne · 发表于 2012-1-13 10:11:19

1# gracias 感觉跟把数完整分解出来好像没啥差别。

wayne · 发表于 2012-1-13 10:17:31

如果是求出幂的和，maple和PARI/Gp 都有一个相关的函数可以用，bigomega ============================= 摘自 PARI/Gp文档： bigomega(x) returns the number of prime divisors of |x|,counting multiplicity. numdiv(x)is the number of divisors of |x|. omega(x) is the number of distinct prime divisors of x.

xbtianlang · 发表于 2012-1-13 11:56:06

没有快速有效的算法吧，[1]就是求某个范围内素数的个数，已经很难了！

gracias · 发表于 2012-1-13 12:00:57

今天什么情况,一下子这么多回复。

zeroieme · 发表于 2012-1-13 12:19:01

没有快速有效的算法吧，[1]就是求某个范围内素数的个数，已经很难了！ xbtianlang 发表于 2012-1-13 11:56

求某个范围内素数的个数有近似公式 n以内的素数个数 $pi(n) ≈n/ln(n)$

wayne · 发表于 2012-1-13 12:34:11

不知道楼主说的“某个范围” 是什么范围

gracias · 发表于 2012-1-13 12:40:03

10^10

mathe · 发表于 2012-1-13 12:42:42

$10^10$范围不大，直接利用不同的p去构造吧

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

[提问] 请教一个问题

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