标签: factorization

有人可以向我解释一种在Python(2.7)中查找数字的所有因子的有效方法吗？

我可以创建算法来完成这项工作,但我认为编码很差,并且执行大量数据的结果需要很长时间.

我写了一个试图找到Amicable Pairs的程序.这需要找到数字的适当除数的总和.

这是我目前的sumOfDivisors()方法:

int sumOfDivisors(int n)
{  
    int sum = 1;
    int bound = (int) sqrt(n);
    for(int i = 2; i <= 1 + bound; i++)
    {
        if (n % i == 0)
            sum = sum + i + n / i;
    } 
    return sum;
}

所以我需要做很多因子分解,这开始成为我应用程序的真正瓶颈.我在MAPLE中输入了一个巨大的数字,它将它快速地考虑在内.

什么是更快的分解算法？

根据这篇文章,我们可以通过以下代码获得数字的所有除数.

for (int i = 1; i <= num; ++i){
    if (num % i == 0)
        cout << i << endl;
}

例如,数字的除数24是1 2 3 4 6 8 12 24.

在搜索了一些相关帖子后,我没有找到任何好的解决方案.有没有有效的方法来实现这一目标？

我的解决方案

1. 通过此解决方案查找给定数字的所有主要因子.
2. 获得这些素因子的所有可能组合.

但是,它似乎不是一个好的.

我正常的搜索foo让我失望.我正在尝试找到一个R函数,它返回整数的所有因子.至少有2个包含factorize()函数的包:gmp和conf.design,但这些函数只返回素因子.我想要一个能够返回所有因子的函数.

显然,搜索这个很困难,因为R有一个叫做因子的结构,它会在搜索中产生很多噪音.

如果您已经对数字进行了素数分解,那么获得该数字的所有因子的最简单方法是什么？我知道我可以从2循环到sqrt(n)并找到所有可分的数字,但这似乎效率低,因为我们已经有了素数分解.

我想它基本上是组合/选择功能的修改版本,但我似乎找到的只是计算组合数量的方法,以及计算因子数量的方法,而不是实际生成组合/因子.

对于库,我需要将第一个素数存储到极限L.此集合必须具有O(1)查找时间(以检查数字是否为素数)并且必须很容易,给定数字,找到下一个素数(假设它小于L).

鉴于L是固定的,生成清单的Eratostene筛子很好.现在,我使用一个打包的布尔数组来存储列表,该列表仅包含3到L(含)之间的奇数的条目.这需要(L-2)/ 2位内存.我希望能够在不使用更多内存的情况下静态增加L.

是否存在使用具有相似属性的较少内存的数据结构？或者至少具有恒定的查找时间？(然后可以枚举奇数,直到我们得到一个素数)

(我在其中编写的语言是因子,但这个问题在内置或易于编程的打包位数组的任何语言中都是相同的)

为了帮助我学习Haskell,我正在研究Project Euler的问题.在解决了每个问题之后,我会针对Haskell wiki检查我的解决方案,以尝试学习更好的编码实践.下面是解决到问题3:

primes = 2 : filter ((==1) . length . primeFactors) [3,5..]

primeFactors n = factor n primes
  where
    factor n (p:ps) 
        | p*p > n        = [n]
        | n `mod` p == 0 = p : factor (n `div` p) (p:ps)
        | otherwise      = factor n ps

problem_3 = last (primeFactors 317584931803)

我对此的天真解读是根据primes定义primeFactors来定义的primes.所以评估primeFactors 9将遵循这个过程:

1. 评估factor 9 primes.
2. 要求primes它的第一个元素,即2.
3. 要求primes它的下一个元素. …

可能的重复:
第n个丑陋的数字
找到表达式的第K个最小数(2 ^ x)*(3 ^ y)*(5 ^ z)

我想知道如何以快速和优雅的方式解决这个问题:

我们定义"丑陋"的每个数字n可以用以下形式写出:2 ^ x*3 ^ y*5 ^ z ;,其中x,y和z是自然数.找到第1500个丑陋的数字.

例如,第一个"丑陋"的数字是:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

我试图用暴力解决这个问题,这样:

import itertools as it

def is_ugly(n):
    '''Return `True` if *n* is an ugly number.'''

    if n == 1:
        return True
    while not n % 2:
        n //= 2
    while not n % 3:
        n //= 3
    while not n % 5:
        n //= 5
    return n …

我正在研究一个需要对整数进行分解的Project Euler问题.我可以得出所有素数的列表,这些素数是给定数字的因子.算术的基本定理意味着我可以使用此列表来推导出数字的每个因素.

我目前的计划是将每个数字放在基本素数列表中并提高其功效,直到它不再是一个整数因子来找到每个素数的最大指数.然后,我将乘以素数指数对的每个可能组合.

例如,对于180:

Given: prime factors of 180: [2, 3, 5]
Find maximum exponent of each  factor: 
    180 / 2^1 = 90
    180 / 2^2 = 45
    180 / 2^3 = 22.5 - not an integer, so 2 is the maximum exponent of 2.

    180 / 3^1 = 60
    180 / 3^2 = 20
    180 / 3^3 = 6.6 - not an integer, so 2 is the maximum exponent of 3.

    180 / 5^1 = 36
    180 …

我是Haskell的新手.

如何生成包含下一个整数的素因子的列表列表？

现在我只知道如何生成素数:

primes = map head $ iterate (\(x:xs) -> [y | y<-xs, y `mod` x /= 0 ]) [2..]