标签: factorization

我设法得到一个Eulers Totient Function的版本,虽然它适用于较小的数字(这里较小的数字比我需要它计算的1024位数字更小)

我的版本在这里 -

public static BigInteger eulerTotientBigInt(BigInteger calculate) { 

    BigInteger count = new BigInteger("0");
    for(BigInteger i = new BigInteger("1"); i.compareTo(calculate) < 0; i = i.add(BigInteger.ONE)) { 
        BigInteger check = GCD(calculate,i);

        if(check.compareTo(BigInteger.ONE)==0)  {//coprime
            count = count.add(BigInteger.ONE);          
        }
    }
    return count;
}

虽然这适用于较小的数字,但它的工作原理是迭代从1到计算的数字.对于大型BigIntegers,这是完全不可行的.

我已经读过,每次迭代都可以划分数字,无需逐个查看.我只是不确定我应该用什么来划分(我在C中看到的一些例子是使用long和一个平方根 - 据我所知我无法准确准确地准确BigInteger的平方根.我也想知道如果对于像这样的模运算,函数是否需要包含一个说明mod是什么的参数.我完全不确定,所以任何建议都非常赞赏.

任何人都能指出我在正确的方向吗？

PS当我发现修改Euler Totient功能时,我删除了这个问题.我改编它与BigIntegers合作 -

public static BigInteger etfBig(BigInteger n) {

    BigInteger result = n;
    BigInteger i;

    for(i = new BigInteger("2"); (i.multiply(i)).compareTo(n) <= 0; i = i.add(BigInteger.ONE)) {
         if((n.mod(i)).compareTo(BigInteger.ZERO) == 0) 
         result = …

任何人都可以推荐一套工具来执行稀疏输入数据[大小为50kx50k的矩阵]的标准NMF应用程序,谢谢!

请你帮助我好吗？

我是C的初学者,我的代码不起作用.

我正在尝试确定最大的素数因子600851475143,当我运行代码时,它什么也没做.尝试使用较小的数字然而有效.

long i;

for (i = 600851475143; i > 1; i--)
{
    if (600851475143 % i == 0)
    {
        printf("%d\n", i);
    }
};

给出一个整数列表(最多1000个)乘以给定的整数n.

我需要在整数的所有除数中找到最高的幂n.

例如:4,7,8乘以224,最高功率则为5,因为224 = 2 ^ 2*7*2 ^ 3 = 2 ^ 5*7.

问题是,1000个整数可以大到2 ^ 64,因此n非常大.

什么是一个很好的算法来解决这个问题？

有没有办法在Perl中轻松分解某些列表？

例如,有2个列表('a', 'b', 'c'),('d', 'e', 'f') 我想要输出('ad', 'ae', 'af' .... 'ce', 'cf')

现在我在做

use strict;
use warnings;

my @listA = ('a', 'b', 'c');
my @listB = ('d', 'e', 'f');
my @listC = ();

foreach my $elementA (@listA)
{
    foreach my $elementB (@listB)
    {
        push(@listC, $elementA.$elementB);
    }
}

这样做很好,但我想知道是否有更"理查"的方式呢？

谢谢 :)

正如Julia的文档(0.6之前)所述,可以使用因子(n)来完成素数因子分解.

它不适用于Julia 0.6.新版本的Julia中是否有任何软件包输出素数因子以及任何给定数字n的arity,因为(n)因子如下所示(来自文档)？

factor(n) ? Dict
Compute the prime factorization of an integer n. 
Returns a dictionary. The keys of the dictionary correspond to the factors, and hence are of the same type as n. 
The value associated with each key indicates the number of times the factor appears in the factorization.

julia> factor(100) # == 2*2*5*5
Dict{Int64,Int64} with 2 entries:
2 => 2
5 => 2

所以我一直在尝试通过解决 Codeforce 上的一些问题来学习 Haskell。
即使我认为我的时间复杂度是最佳的，我也得到了很多 TLE（超出时间限制）。

我的问题是：是我编写这个程序的方式使它变慢了吗？

例如，这里是问题。

基本上答案是找到给定的，其中 and =和之间的除数数之差。annan = 2*an-1 + D(n)D(n)nn-1

（更新：上限为n10 ⁶）。

下面是我的程序。

import qualified Data.Map.Strict as Map

main = do t <- read <$> getLine
          putStrLn . show $ solve t

solve :: Integer -> Integer
solve 0 = 1
solve 1 = 1
solve n = (2*(solve (n-1)) + (fact n) - (fact (n-1))) `mod` 998244353
    where fact …