c# - 有效地找到一个数字的所有约数

coder 2024-05-30 原文

所以我只想找到给定数字的所有除数(数字本身除外)。目前，我有这个:

public static List<int> proper_divisors(int x)
{
    List<int> toreturn = new List<int>();
    toreturn.Add(1);
    int i = 0;
    int j=1;
    int z = 0;
    while (primes.ElementAt(i) < Math.Sqrt(x))
    {
        if (x % primes.ElementAt(i) == 0)
        {
            toreturn.Add(primes.ElementAt(i));
            toreturn.Add(x / primes.ElementAt(i));
            j = 2;
            z = (int)Math.Pow(primes.ElementAt(i), 2);
            while (z < x)
            {
                if (x % z == 0)
                {
                    toreturn.Add(z);
                    toreturn.Add(x / z);
                    j++;
                    z = (int)Math.Pow(primes.ElementAt(i), j);
                }
                else
                {
                    z = x;
                }
            }
        }
        i++;
    }
    toreturn = toreturn.Distinct().ToList<int>();
    return toreturn;
}

其中 primes 是一个素数列表(假设它是正确的，并且足够大)。该算法的工作原理是它找到所有素因子，但不是所有因子(即给定 34534，它返回 {1,2,17267,31,1114} 但错过 {62, 557} 因为 62 是一个组合，因此也错过了 557。

我也试过只获取一个数的质因数，但我不知道如何将其转换为所有正确组合的列表。

该算法的代码如下:

public static List<int> prime_factors(int x)
{
    List<int> toreturn = new List<int>();
    int i = 0;
    while (primes.ElementAt(i) <= x)
    {
        if (x % primes.ElementAt(i) == 0)
        {
            toreturn.Add(primes.ElementAt(i));
            x = x / primes.ElementAt(i);
        }
        else
        {
            i++;
        }
    }
    return toreturn;
}

关于如何修复第一个，或者如何从第二个创建组合列表的任何想法(我更喜欢这样，因为它会更快)？

最佳答案

既然您已经有了一个素因子列表，您要做的就是计算该列表的幂集。

现在，一个问题是列表中可能有重复项(例如 20 的质因数 = 2 * 2 * 5)，但集合不允许重复项。因此，我们可以通过将列表中的每个元素投影到 {x, y} 形式的结构来使列表中的每个元素唯一，其中 x 是素数，y 是素数在列表中的索引。

var all_primes = primes.Select((x, y) => new { x, y }).ToList();

现在，all_primes是 {x, y} 形式的列表，其中 x 是素数，y 是列表中的索引。

然后我们计算幂集(下面 GetPowerSet 的定义):

var power_set_primes = GetPowerSet(all_primes);

因此，power_set_primes是一个 IEnumerable<IEnumerable<T>>其中 T是匿名类型 {x, y}其中 x 和 y 的类型为 int .

接下来，我们计算幂集中每个元素的乘积

foreach (var p in power_set_primes)
{
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y);
    factors.Add(factor);
}

综合起来:

var all_primes = primes.Select((x, y) => new { x, y }).ToList(); //assuming that primes contains duplicates.
var power_set_primes = GetPowerSet(all_primes);
var factors = new HashSet<int>();

foreach (var p in power_set_primes)
{
    var factor = p.Select(x => x.x).Aggregate(1, (x, y) => x * y);
    factors.Add(factor);
}

来自 http://rosettacode.org/wiki/Power_Set用于 powerset 的实现。

public IEnumerable<IEnumerable<T>> GetPowerSet<T>(List<T> list)
{
    return from m in Enumerable.Range(0, 1 << list.Count)
           select
               from i in Enumerable.Range(0, list.Count)
               where (m & (1 << i)) != 0
               select list[i];
}

关于c# - 有效地找到一个数字的所有约数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5793009/

c#有效 primes code toreturn prime-factoring factorization

有关c# - 有效地找到一个数字的所有约数的更多相关文章

ruby - 如何以所有可能的方式将字符串拆分为长度最多为 3 的连续子字符串？ - 2
我试图获取一个长度在1到10之间的字符串，并输出将字符串分解为大小为1、2或3的连续子字符串的所有可能方式。例如:输入:123456将整数分割成单个字符，然后继续查找组合。该代码将返回以下所有数组。[1,2,3,4,5,6][12,3,4,5,6][1,23,4,5,6][1,2,34,5,6][1,2,3,45,6][1,2,3,4,56][12,34,5,6][12,3,45,6][12,3,4,56][1,23,45,6][1,2,34,56][1,23,4,56][12,34,56][123,4,5,6][1,234,5,6][1,2,345,6][1,2,3,456][123
ruby - 使用 Vim Rails，您可以创建一个新的迁移文件并一次性打开它吗？ - 2
使用带有Rails插件的vim，您可以创建一个迁移文件，然后一次性打开该文件吗？textmate也可以这样吗？最佳答案你可以使用rails.vim然后做类似的事情::Rgeneratemigratonadd_foo_to_bar插件将打开迁移生成的文件，这正是您想要的。我不能代表textmate。关于ruby-使用VimRails，您可以创建一个新的迁移文件并一次性打开它吗？，我们在StackOverflow上找到一个类似的问题： https://sta
ruby-on-rails - Rails - 一个 View 中的多个模型 - 2
我需要从一个View访问多个模型。以前，我的links_controller仅用于提供以不同方式排序的链接资源。现在我想包括一个部分(我假设)显示按分数排序的顶级用户(@users=User.all.sort_by(&:score))我知道我可以将此代码插入每个链接操作并从View访问它，但这似乎不是“ruby方式”，我将需要在不久的将来访问更多模型。这可能会变得很脏，是否有针对这种情况的任何技术？注意事项:我认为我的应用程序正朝着单一格式和动态页面内容的方向发展，本质上是一个典型的网络应用程序。我知道before_filter但考虑到我希望应用程序进入的方向，这似乎很麻烦。最终从任何
ruby-on-rails - 渲染另一个 Controller 的 View - 2
我想要做的是有2个不同的Controller，client和test_client。客户端Controller已经构建，我想创建一个test_clientController，我可以使用它来玩弄客户端的UI并根据需要进行调整。我主要是想绕过我在客户端中内置的验证及其对加载数据的管理Controller的依赖。所以我希望test_clientController加载示例数据集，然后呈现客户端Controller的索引View，以便我可以调整客户端UI。就是这样。我在test_clients索引方法中试过这个:classTestClientdefindexrender:template=>
ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象，为什么它会起作用？ - 2
如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？最佳答案像Ruby中的所有其他对象
ruby - 为什么 SecureRandom.uuid 创建一个唯一的字符串？ - 2
关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion为什么SecureRandom.uuid创建一个唯一的字符串？SecureRandom.uuid#=>"35cb4e30-54e1-49f9-b5ce-4134799eb2c0"SecureRandom.uuid方法创建的字符串从不重复？
ruby - 如何进行排列以有效地定制输出 - 2
这是一道面试题，我没有答对，但还是很好奇怎么解。你有N个人的大家庭，分别是1,2,3,...,N岁。你想给你的大家庭拍张照片。所有的家庭成员都排成一排。“我是家里的friend，建议家庭成员安排如下:”1岁的家庭成员坐在这一排的最左边。每两个坐在一起的家庭成员的年龄相差不得超过2岁。输入:整数N，1≤N≤55。输出:摄影师可以拍摄的照片数量。示例->输入:4，输出:4符合条件的数组:[1,2,3,4][1,2,4,3][1,3,2,4][1,3,4,2]另一个例子:输入:5输出:6符合条件的数组:[1,2,3,4,5][1,2,3,5,4][1,2,4,3,5][1,2,4,5,3][
ruby-on-rails - 跳过状态机方法的所有验证 - 2
当我的预订模型通过rake任务在状态机上转换时，我试图找出如何跳过对ActiveRecord对象的特定实例的验证。我想在reservation.close时跳过所有验证!叫做。希望调用reservation.close!(:validate=>false)之类的东西。仅供引用，我们正在使用https://github.com/pluginaweek/state_machine用于状态机。这是我的预订模型的示例。classReservation["requested","negotiating","approved"])}state_machine:initial=>'requested
ruby - Nokogiri 剥离所有属性 - 2
我有这个html标记:我想得到这个:我如何使用Nokogiri做到这一点？最佳答案 require'nokogiri'doc=Nokogiri::HTML('')您可以通过xpath删除所有属性:doc.xpath('//@*').remove或者，如果您需要做一些更复杂的事情，有时使用以下方法遍历所有元素会更容易:doc.traversedo|node|node.keys.eachdo|attribute|node.deleteattributeendend 关于ruby-Nokog
ruby-on-rails - Rails - 从另一个模型中创建一个模型的实例 - 2
我有一个正在构建的应用程序，我需要一个模型来创建另一个模型的实例。我希望每辆车都有4个轮胎。汽车模型classCar轮胎模型classTire但是，在make_tires内部有一个错误，如果我为Tire尝试它，则没有用于创建或新建的activerecord方法。当我检查轮胎时，它没有这些方法。我该如何补救？错误是这样的:未定义的方法'create'forActiveRecord::AttributeMethods::Serialization::Tire::Module我测试了两个环境:测试和开发，它们都因相同的错误而失败。最佳答案

c# - 有效地找到一个数字的所有约数

有关c# - 有效地找到一个数字的所有约数的更多相关文章

随机推荐