问题标签 [factorization]

我正在用 java 编写一个程序，该程序可以计算给定值的 sqrt 高达 10^100 。为此，我知道我必须使用 BigInteger，但我正在处理的过程效率不高，因为它需要很多时间。分解一个数字以处理程序的最快过程是什么？更快的算法是什么？

提前致谢。

在我因为不遵守规则而受到抨击之前，我确实使用了搜索功能，并看到这个问题有多个线程。但是，他们都没有回答我的具体问题。

我正在研究欧拉问题#3，我需要找到 600851475143 的最高素数。我不需要帮助来解决问题。我已经提出了一种蛮力方法（我知道可能会更好）来解决它。

对于我使用较小数字（7 位数及以下）所做的所有测试，该程序都会正确返回。但是，当我输入 600851475143 作为长输入时，我的程序永远不会给我返回。我的号码是否太大而无法输入？什么可能导致这种情况发生？我最初认为这是因为我使用的是 int 标签而不是 long，但更改这些标签并没有改变我的结果。

我确信这很简单，我很想念它，但我很好奇发生了什么。先感谢您 ：）

我正在尝试使用 python 库Nimfa分解非常大的矩阵。由于矩阵太大，我无法在内存中以 dence 格式实例化它，所以我使用scipy.sparse.csr_matrix。

该库有一个称为Snmf: Sparse Nonnegative Matrix Factorization (SNMF)的稀疏矩阵函数，这似乎是我正在寻找的。

尝试它时，我在分解时遇到了严重的性能问题（不是内存表示，而是速度），我还不能分解一个简单的 10 x 95 稀疏矩阵。

这就是我构建测试矩阵的方式：

这就是我运行它的方式

这似乎根本没有完成。但是如果我做 m1.todense() 它会在几秒钟内完成。由于我无法实例化我的真实矩阵，这对我来说并不是一个好的解决方案。

我尝试了不同的 scipy.sparse 矩阵格式但无济于事：csc_matrix、csr_matrix 和 dok_matrix。

我使用了错误的矩阵格式吗？snmf算法需要哪些矩阵运算才能快速执行？还有其他一些我忽略的错误吗？

我一直在研究一个数学问题：找出大数的因数。我已经了解了“素数分解”的方法，这一切都很好地用于 php 中的代码。但是，假设我想知道数字 196 的因数（即：1、2、4、7、14、28、49、98、196），我发现这个数字的素数分解是：（ 2^2)(7^2)。

要找到这些因素，您必须在两者之间进行所有可能的组合并将它们相乘：

这就是我卡住的地方。我需要找到一个可以组合这些项目的函数（指数可能不会高于那个数字的素数分解）。此函数必须对 N 个因子起作用（N 是一个 > 0 且小于 100 的数字）。

我希望你能理解我的问题，并对如何解决它有一些想法！

所以我现在正在研究一个java代码。我已经让它工作得很好，但是任务的重点是让它分解大数字（超过 30 位）。它会这样做，但是它可能需要超过 15 分钟才能完成，这是不好的。我的教授向我保证，我使用的算法适用于高达 2^70 的数字，并且应该在大约五分钟内完成。我一直在尝试想出一种方法来做到这一点（增加 2 而不是 1 等），但我似乎无法弄清楚如何在不跳过某些因素的情况下让它更快地移动。有任何想法吗？我还认为椭圆曲线法会更好，但他告诉我现在不要处理这个问题。

这是我的代码（ps，sqrt 是我自己的函数，但我确信它正在工作）：

我正在尝试将一段简单的数学转换为 Linq。

我想将几个数字的主要因素捆绑到一个集合中。考虑以下整数。

能被 8 和 12 整除的最小数是 24，所以我希望结果组包含

如果我使用Concat结果是 {2,2,2,2,2,3} - 不正确如果我使用Union结果是 {2,3} - 不正确

是否有一个内置的 Linq Set Manipulation 函数，它将认识到它需要保持一个项目的最大出现次数（即，如果已经有足够的数量来满足，则不要添加另一个，如果没有，则添加另一个）

Everytime I try to solve some math problem such as finding a specific product of certain number of factors I do this in Python

It is very straightforward and gets the job done fast in this example, but I was wondering if you guys know an easier or simpler way to write this. Any ideas on how to do this without using that many for iterations or repeating almost the same code over and over. These is obviously for 3 factors, but the more factors I add the longer and more repetitive the code keeps getting. Any ideas on how to simplify code for this simple type of problem? thanks

我正在寻找用于快速素性测试和大数分解的 Java API。任何指针都会对我很有帮助。

更新

我找到的资源是：

• BigInteger - 没有分解
• Primes - 处理整数
• LargeInteger - 没有分解

我期待使用Elliptic Curve Factorization或Quadratic Sieve的 API 。

另一个资源：使用椭圆曲线方法进行分解。

限制：10000 位数字。

I am coding a program to factor a number into is prime factors. The program works as follows:

1) Input a number that you wish to factor (I will refer to is as "inputNumber")

2) Test to see if you can divide inputNumber by 2,3,5 and 7 (first 4 prime numbers). if you can divide by any of these, then do so as many times as you can (i.e. 12 can be divided by 2 twice, after this, there is a remainder of 3) note every time I divide by a number, I store that number in an array list and I keep the remainder for further testing

3) Starting with i=11 (the next prime number) in a while loop, I do the following:

this way, every successful iteration of the while loop will divide the remainder by numbers finishing by 1,3,7,9. We do not need to test even numbers since we divided by 2 already, nor do we need to test the ones ending by 5 since we already divided by 5. In the end, we

This is a very neat algorithm since it its much much faster than factoring a number by testing one number after the other, in fact, you only need to test 40% of all numbers.

My question is: When I tried factoring 84738329279, a number picked randomly, it omits to put the last prime factor in the list, I can't quite figure this out. the only factors that show up are 41, 61 and 61. Can someone help me find what I'm doing wrong? here is my code:

Thanks in advance.

我是编程新手，我正在尝试编写一个程序，该程序从输入中获取一个正整数 n，然后输出 n 的所有因式分解。

例如，如果 n=10，程序将输出
1 乘以 10 等于 10
2 乘以 5 等于 10
5 乘以 2 等于 10
10 乘以 1 等于 10

我相信最简单的方法是使用嵌套在 for 循环中的 if 语句。任何人都可以为我提供任何指导来帮助创建这个吗？到目前为止，我已经...

但由于某种原因，它不起作用。我认为我的总体思路是正确的，但我的代码显然不正确。