如何测试非常大的整数是否只有 2、3 和 7 的素因子？
How do I test whether VERY large integers have prime factors that are only 2s, 3s, and 7s?
我正在处理非常大的整数，以 10 为基数大约有 30000 个数字。大多数数字是 1，但少数（少于 20 位）不是 1。
我只关心这些数字，如果它们的质因数分解仅由 2、3 和 7 组成。我确定这个数字不能被 5 整除，因为它不能以 0 或 5 结尾，所以我不需要检查它。
我希望能够取这个非常大的整数，如果它可以被 2 整除，我将它重复除以 2，直到结果不能再被 2 整除。然后，如果结果可以被 3 整除，我重复除以 3，直到结果不能被 3 整除。最后，如果结果能被 7 整除，我重复除以 7，直到结果不能被 7 整除。如果最后的结果是 1，那么我知道原数的质因数只有2s、3s、7s，也就是我要找的属性。
我的问题：
- Is this a good way to test whether a large number has prime factors that are only 2s, 3s, and 7s? If not, is there a more efficient way to test this?
- What is the least costly way to store these VERY large (~30000 digits) integers? I only care about testing whether these large integers have prime factors other than 2, 3, 7. I'm open to using Java, Python, C++, C, whichever of these common languages will give me the most efficient possible search.
我通过搜索找到的东西：
许多语言都有一个 "BigInteger" 类型，它可能仅受可用内存的限制。这听起来不错，但我认为以 10 为基数的 ~30000 位数字对应于该整数的大量内存。我不确定是否有更聪明的方法来处理这个问题。
数学家称属性我正在测试“7-smoothness”。如果一个正整数没有大于 7 的质因数，则它是 7-smooth。我已经知道我要测试的数字不能被 5 整除，所以我真的只寻找 2s、3s 和 7s。
我更像是一名数学家而不是计算机科学家，所以我对这种计算优化很陌生。
感谢任何帮助:)
有趣的问题。让我们拨打有问题的号码 X.
Is this a good way to test whether a large number has prime factors
that are only 2s, 3s, and 7s?
您概述的方法似乎是最好的，既快速又易于理解。另一种方法是计算 X 和 2*3*7 的最小公倍数。如果结果是 X，则 X 完全由 2、3、7 的幂组成。但是，我认为 LCM 方法的计算复杂度 不如。
What is the least costly way to store these VERY large (~30000 digits)
integers.
30000 位数字比密码学中通常使用的数字大，但在我所知道的任何系统上都不是例外。它只需要大约 13k 字节的 base-2 存储空间，几乎不值得考虑。
不幸的是，"best" 存储整数的方法稍微复杂一些，因为它取决于数据的来源和去向。大整数通常以二进制格式存储，并且还取决于您如何定义成本。这种格式可以称为base 2，但更准确的是它通常存储为一个base 2w"words"或"limbs"的序列，其中w是一个方便的大小用于进行基本的算术运算。例如w经常取32或64，有时会比32或64小几位，所以w乘以w一个 64 位或 128 位类型的字可以容纳大量进位。
这种以 2 为底的表示形式是我见过的唯一一种用于一般大整数包的形式*。它使得计算除 X 的 2 的最大次方特别高效。如果您编写自己的代码，则可以选择其他基数进行存储，例如，在您的情况下，您可以选择基数 5 或基数 7 或基数 2*3*7=42.
base 的选择还应该考虑数据是如何进入的，因为如果输入是在底层包的 base 之外的其他东西中提供的，那么将数据从输入源转换为大整数源可能会很昂贵.
* 还有大十进制包可以将数据存储在基数 10 而不是基数 2，方便确定 X 中 5 或 10 的幂。你' d 必须检查大十进制实现的细节以确定它是否真的更快，而且你对 5 或 10 的幂不感兴趣。
我正在处理非常大的整数，以 10 为基数大约有 30000 个数字。大多数数字是 1，但少数（少于 20 位）不是 1。
我只关心这些数字，如果它们的质因数分解仅由 2、3 和 7 组成。我确定这个数字不能被 5 整除，因为它不能以 0 或 5 结尾，所以我不需要检查它。
我希望能够取这个非常大的整数，如果它可以被 2 整除，我将它重复除以 2，直到结果不能再被 2 整除。然后，如果结果可以被 3 整除，我重复除以 3，直到结果不能被 3 整除。最后，如果结果能被 7 整除，我重复除以 7，直到结果不能被 7 整除。如果最后的结果是 1，那么我知道原数的质因数只有2s、3s、7s，也就是我要找的属性。
我的问题：
- Is this a good way to test whether a large number has prime factors that are only 2s, 3s, and 7s? If not, is there a more efficient way to test this?
- What is the least costly way to store these VERY large (~30000 digits) integers? I only care about testing whether these large integers have prime factors other than 2, 3, 7. I'm open to using Java, Python, C++, C, whichever of these common languages will give me the most efficient possible search.
我通过搜索找到的东西：
许多语言都有一个 "BigInteger" 类型，它可能仅受可用内存的限制。这听起来不错，但我认为以 10 为基数的 ~30000 位数字对应于该整数的大量内存。我不确定是否有更聪明的方法来处理这个问题。
数学家称属性我正在测试“7-smoothness”。如果一个正整数没有大于 7 的质因数，则它是 7-smooth。我已经知道我要测试的数字不能被 5 整除，所以我真的只寻找 2s、3s 和 7s。
我更像是一名数学家而不是计算机科学家，所以我对这种计算优化很陌生。
感谢任何帮助:)
有趣的问题。让我们拨打有问题的号码 X.
Is this a good way to test whether a large number has prime factors that are only 2s, 3s, and 7s?
您概述的方法似乎是最好的，既快速又易于理解。另一种方法是计算 X 和 2*3*7 的最小公倍数。如果结果是 X，则 X 完全由 2、3、7 的幂组成。但是，我认为 LCM 方法的计算复杂度 不如。
What is the least costly way to store these VERY large (~30000 digits) integers.
30000 位数字比密码学中通常使用的数字大，但在我所知道的任何系统上都不是例外。它只需要大约 13k 字节的 base-2 存储空间，几乎不值得考虑。
不幸的是，"best" 存储整数的方法稍微复杂一些，因为它取决于数据的来源和去向。大整数通常以二进制格式存储，并且还取决于您如何定义成本。这种格式可以称为base 2，但更准确的是它通常存储为一个base 2w"words"或"limbs"的序列，其中w是一个方便的大小用于进行基本的算术运算。例如w经常取32或64，有时会比32或64小几位，所以w乘以w一个 64 位或 128 位类型的字可以容纳大量进位。
这种以 2 为底的表示形式是我见过的唯一一种用于一般大整数包的形式*。它使得计算除 X 的 2 的最大次方特别高效。如果您编写自己的代码，则可以选择其他基数进行存储，例如，在您的情况下，您可以选择基数 5 或基数 7 或基数 2*3*7=42.
base 的选择还应该考虑数据是如何进入的，因为如果输入是在底层包的 base 之外的其他东西中提供的，那么将数据从输入源转换为大整数源可能会很昂贵.
* 还有大十进制包可以将数据存储在基数 10 而不是基数 2，方便确定 X 中 5 或 10 的幂。你' d 必须检查大十进制实现的细节以确定它是否真的更快，而且你对 5 或 10 的幂不感兴趣。