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具体是多少而只考虑其最后分解结果中不同素因子的个数及其幂.
例如用$$表示一个数含有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

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

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

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

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

没有快速有效的算法吧，就是求某个范围内素数的个数，已经很难了！
xbtianlang 发表于 2012-1-13 11:56 http://bbs.emath.ac.cn/images/common/back.gif

求某个范围内素数的个数有近似公式
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去构造吧
页: [1]
查看完整版本: 请教一个问题