程序员经验分享-hwhale

大数的质因数分解

2024-02-05

我正在尝试找出大数因式分解的复杂性。 哪种算法是最好的？查找数字质因数的复杂度是多少？假设数字的长度为n。


最著名的大于 100 位整数因式分解算法是通用数域筛 http://en.wikipedia.org/wiki/General_number_field_sieve。它的复杂性在链接链接到的页面上进行了解释。

维基百科有一篇关于其他算法的好文章：http://en.wikipedia.org/wiki/Integer_factorization http://en.wikipedia.org/wiki/Integer_factorization

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

primes

primefactoring

大数的质因数分解 的相关文章

  • 使用 SIMD 查找素数列表 - SSE/AVX

    我很好奇是否有人对如何使用 SIMD 查找素数列表有建议 我特别感兴趣如何使用 SSE AVX 来做到这一点 我一直在研究的两种算法是试除法和埃拉托斯特尼筛法 我设法找到一种使用 SSE 进行试除的方法 我找到了一种更快的除法方法 该方法非

  • 使用列表理解进行素因数分解

    我想仅使用列表理解方法和 或找到给定数字的所有素因数 Haskell 中的 函数组合运算符 我特别想避免递归解决方案 例如 pfactors 120必须产生 2 2 2 3 5 output I tried pfactors n p p l

  • 埃拉托斯特尼筛法 - 寻找素数 Python

    只是澄清一下 这不是作业问题 我想为我正在构建并遇到的数学应用程序找到素数埃拉托斯特尼筛法方法 我已经用 Python 编写了它的实现 但速度非常慢 比如说 如果我想找到所有小于 200 万的素数 需要 gt 20 分钟 我此时停止了 我怎

  • 给定一个数字 X，估计该数字可能落在素数的有序列表中的哪个位置

    给定预先计算的素数有序列表和提供的数字 X 我想粗略估计 X 在素数列表中的位置 并从该点开始搜索 因此 我计算了 1 2 32 1 中的素数列表并将其存储在二进制文件中 我在一个针对该文件运行的程序中提供了一些方法 可以给我第 n 个素数

  • Haskell 中的素筛

    我对 Haskell 很陌生 我只是想找到前 200 万个素数的总和 我正在尝试使用筛子生成素数 我认为埃拉托色尼筛子 但它真的很慢 我不知道为什么 这是我的代码 sieve x xs x sieve filter a gt a mod x

  • 查找给定数字之后的质数

    如何找到大于给定数字的最小素数 例如 给定 4 我需要 5 给定 7 个 我需要 11 个 我想知道一些关于最佳算法的想法 我想到的一种方法是通过埃拉托色尼筛生成素数 然后找到给定数后面的素数 Source 维基百科 伯特兰公设 http

  • R-莱曼素性测试中的模数警告

    我花了一点时间破解莱曼素性测试的 R 实现 我借鉴的功能设计http davidkendal net articles 2011 12 lehmann primality test http davidkendal net articles

  • 面试问题：递归生成素数最快的方法是什么？ [关闭]

    就目前情况而言 这个问题不太适合我们的问答形式 我们希望答案得到事实 参考资料或专业知识的支持 但这个问题可能会引发辩论 争论 民意调查或扩展讨论 如果您觉得这个问题可以改进并可能重新开放 访问帮助中心 help reopen questi

  • “e 是 65537 (0x10001)”是什么意思？

    我想知道输出是什么e is 65537 0x10001 方法 它发生在 RSA 密钥生成过程中 使用openssl genrsa 我知道这些点意味着该数字已经通过了探针除法 并且在通过米勒 拉宾测试后打印出了加号 但我无法弄清楚 RSA 密

  • JavaScript：使用递归检查数字是否为素数

    我对如何解决这个问题有点困惑 我需要所有素数才能返回 true 如果不返回 false 我看到我的逻辑包括 2 并且返回 0 所以它自动返回 false 因为 2 余数为 0 function isPrime num div 2 BASE

  • 如何编写一个快速函数来计算数字的总除数？

    我必须找到给定数字 N 的除数总数 其中可以大到 10 14 我尝试计算最多 10 7 的素数 然后使用素数因子的指数找到除数 但是事实证明它太慢了 因为使用筛子找到素数需要 0 03 秒 如果可能的话 如何更快地计算除数总数而不计算素数

  • 对 99 位数字长的大数进行因式分解的问题

    号码是 112887987371630998240814603336195913423482111436696007401429072377238341647882152698281999652360869 我的代码如下 def getfa

  • 就空间而言最快的方法——用Python找到素数

    也许这是一个愚蠢的问题 但我想知道你是否可以提供用Python查找素数的最短来源 我还想知道如何使用 map 或 filter 函数查找素数 谢谢 编辑 当我说最快 最短时 我的意思是使用较少字符 单词的方式 无论如何 不 要考虑竞争 我想

  • 对小数的最快素数测试

    我在业余时间玩了 Euler 项目 现在我需要做一些重构 我已经实施了 Miller Rabin 以及一些筛子 我以前听说过 对于较小的数量 例如数百万以下 筛子实际上更快 有人有这方面的信息吗 谷歌并没有多大帮助 Yes you ll f

  • Clojure：避免埃拉托斯特尼筛中的堆栈溢出？

    这是我在 Clojure 中实现的埃拉托斯特尼筛法 基于 SICP 流课程 defn nats from n iterate inc n defn divide p q zero rem q p defn sieve stream lazy

  • 从数组中打印素数

    我想用方法从数组中打印出所有素数 我可以用一个 int 来完成 但不知道如何从数组中返回某些数字 感谢帮助 public static boolean isPrime int tab boolean prime true for int i

  • Haskell：Data.Numbers.Primes 库在哪里？

    我尝试导入 Data Numbers Primes import Data Numbers Primes 伦哈斯克尔给了我 5 hs 1 8 Could not find module Data Numbers Primes Use v t

  • 在编译时生成素数

    我对如何在编译时生成素数数组感兴趣 我相信唯一的方法是使用元编程 在 C 中 不确定这在其他语言中如何工作 快速说明 我不想只是说int primes x 2 3 5 7 11 因为我想在竞争性编程中使用这种方法 其中源文件不能大于10KB

  • 打印从 1 到 100 的质数

    此 C 代码打印出以下素数 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 但我不认为这就是我的书所希望的写作方式 它提到了一些关于数字的平方根的内容

  • 埃拉托斯特尼筛法是生成 1 到 N 素数的最佳算法吗？

    我在一次采访中被问到这个问题 我使用埃拉托色尼筛子概念和数组实现了一种算法 有没有更好的方法来解决这个问题 对于不知道筛子的人 请点击以下链接 http en wikipedia org wiki Sieve of Eratosthenes

随机推荐

  • 有效连接多个 sas 数据集

    我有超过 200k 个具有相同变量 n macro catDat name nbr call in new dataset data new set libin name run reorder names proc sql noprint

  • ie11 的 CSS 自定义属性 polyfill

    有没有办法用 JavaScript 来 pollyfill ie11 的自定义 CSS 属性 我在考虑加载 检查浏览器是否支持自定义属性 如果不支持 则对属性进行某种查找和替换 这可以通过 JavaScript 或某些库实现吗 Thanks

  • 客户端 javascript 相当于 Lucene

    我想知道是否有一个相当于 Lucene API 的 Javascript 旨在用于客户端来索引相对较小的数据集 一个示例用例是静态站点 例如生成的 能够搜索内容而无需服务器端处理 我发现了这个 http lunrjs com http lu

  • Asp.net 验证错误消息更改标签文本

    我正在使用 asp net 验证控件来验证用户输入 我想要的是使用验证控件生成的错误消息更改标签文本

  • 角度 (1.5.8) 动态组件

    我正在尝试使用 Angular 1 5 8 构建一种动态仪表板 直到最后一个障碍 我已经取得了不错的进步 这实际上是在渲染动态组件 我尝试了 2 个选项 要么添加一个ui view并以编程方式传递小部件的名称 or 这就是我猜的路线more

  • 将参数从父函数传递给嵌套函数Python

    这是我的代码 def f x def g n if n lt 10 x x 1 g n 1 g 0 当我评估 f 0 时 会出现错误 赋值前引用了 x 但是 当我使用 print x 而不是 x x 1 时 它会起作用 看来在 g 的范围内

  • C# 定时器或 Thread.Sleep

    我正在运行 Windows 服务并使用循环和 Thread Sleep 来重复任务 使用计时器方法会更好吗 如果是的话 代码示例会很棒 我目前正在使用此代码来重复 int curMinute int lastMinute DateTime

  • 枚举的通用类，值的数量

    我如何知道我的枚举在此示例中有多少个值 public class Analyser

  • 如何使用服务的输入/输出动态创建组件实例并将其单独注入到 DOM 中？

    在 Angular 2 中创建动态组件时 我found https stackoverflow com questions 36325212 angular 2 dynamic tabs with user click chosen com

  • 将表单和框架添加到包中

    我正在开发一个 IDE 注册组件包 其中大部分都派生自 TFrame 基类 包中还包含这些组件调用的各种自定义对话框表单 我在 Delphi 2007 工作 我注意到 有时框架和表单单元 通常具有关联的 DFM 文件 并不总是在其下方 下方

  • WSO2 EMM：从设备管理中删除设备

    我成功将 Android 设备注册到 EMM 然后我恢复出厂设置并重新注册 现在 同一设备在我的设备管理中列出了两次 第一件事 这种行为是想要的吗 我认为应该有一个规则来检查 IMEI 并用新注册的对象替换旧对象 第二件事 如何摆脱旧对象

  • tidyverse 中多个群体的引导：rsample 与 broom

    In 这个问题 https stackoverflow com questions 42986736 bootstrapping by multiple groups in dplyr由几个小组和子小组进行引导似乎很容易使用broom bo

  • urllib 异常 http.client.BadStatusLine

    我一生都无法弄清楚为什么我不能捕获这个异常 看着这里本指南 https docs python org 3 howto urllib2 html def get team names get team id url team id prin

  • 错误 404 的默认重定向

    我想在我的 ASP net 网站中引入一项功能 每当收到对我的域中未知 URL 的请求时 用户就会被重定向到我的网站error 404 htm应用程序根目录中的页面 例如 如果请求是http www mydomain com blahbla

  • System.IO.ReadAllxxx / WriteAllxxx 方法的性能

    是否有 System IO File ReadAllxxx WriteAllxxx 方法与 Web 上提供的 StreamReader StremWriter 类的性能比较 您认为在 net 3 0 中读取 写入文本文件的最佳方式 从性能角

  • Cloud Functions 中的 Cloud Firestore

    我想将新的 Cloud Firestore 集成到我的 Cloud Functions 中 我更新了 node js 并在我的 Mac 上安装了最新的 firebase 版本 文档说 exports myFunctionName funct

  • 如何在 React 应用程序中处理 Firebase onAuthStateChanged 并相应地路由用户？

    我正在开发一个与 Firebase 集成的 React Web 应用程序 并且我正在尝试对我的用户进行身份验证 我已经设置了路线 以便在用户通过身份验证时显示主页组件 否则显示登录页面 但是 当我的应用程序首次加载时 它会显示登录页面 需要

  • 数据框的小提琴图

    我有一个data frame 例如 df data frame AAA rnorm 100 1 1 BBB rnorm 100 2 1 5 CCC rnorm 100 1 5 1 2 我想在联合小提琴图中绘制它的每个列 这是我目前所处的位置

  • 计算 sf 线串与 r 中的网格单元相交的次数

    考虑一组线串和一个多边形网格 sf 几何 library sf creating data example id lt c 844 844 844 844 844 855 855 855 855 855 lat lt c 30 6456 2

  • 大数的质因数分解

    我正在尝试找出大数因式分解的复杂性 哪种算法是最好的 查找数字质因数的复杂度是多少 假设数字的长度为n 最著名的大于 100 位整数因式分解算法是通用数域筛 http en wikipedia org wiki General number

热门标签