2

我想知道是否有一种算法可以检查给定数字是否可分解为一组素数，如果没有则给出最接近的数字。当我使用 FFT 时，问题总是出现。

非常感谢你们的帮助。

4

5 回答 5

2

一般来说，这看起来像是一个难题，尤其是找到下一个最大的整数，该整数会影响您的素数集。但是，如果您的素数集不是太大，一种方法是通过获取日志将其转换为整数优化问题。以下是如何找到最小的数 > n 将其分解为一组素数 p_1...p_k

choose integers x_1,...,x_k to minimize (x_1 log p_1 + ... + x_k log p_k - log n)
Subject to:
  x_1 log p_1 + ... + x_k log p_k >= log n
  x_i >= 0 for all i

x_i 将为您提供素数的指数。这是使用 lpSolve 在 R 中的实现：

minfact<-function(x,p){
  sol<-lp("min",log(p),t(log(p)),">=",log(x),all.int=T)
  prod(p^sol$solution)
}

> p<-c(2,3,13,31)
> x<-124363183
> y<-minfact(x,p)
> y
[1] 124730112
> factorize(y)
Big Integer ('bigz') object of length 13:
 [1] 2  2  2  2  2  2  2  2  3  13 13 31 31
> y-x
[1] 366929
>

使用大整数，即使对于大数也能很好地工作：

> p<-c(2,3,13,31,53,79)
> x<-as.bigz("1243631831278461278641361")
> y<-minfact(x,p)
y
> 
Big Integer ('bigz') :
[1] 1243634072805560436129792
> factorize(y)
Big Integer ('bigz') object of length 45:
 [1] 2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2  2 
[26] 2  2  2  2  2  2  2  2  3  3  3  3  13 31 31 31 31 53 53 53
>
于 2013-10-09T14:16:08.323 回答
2

您的问题是关于众所周知的分解问题- 无法用“快速”（多项式）时间解决。Lenstra 的椭圆算法是常见情况下最有效（已知）的方法，但它需要强大的数论知识 - 而且它也是次指数（但不是多项式）。

其他算法在我的帖子中的第一个链接的页面中列出，但是直接尝试（蛮力）之类的事情要慢得多，这是有原因的。

请注意，在“无法用多项式时间解决”下 - 我的意思是现在没有办法做到这一点-但并不是说这种方式不存在（至少现在，数论无法为这个问题提供这样的解决方案)

于 2013-10-09T13:20:41.313 回答
1

这是C ++中的蛮力方法。它返回最近的可因式数的因式分解。如果 N 有两个等距的可分解邻居，则返回最小的邻居。

GCC 4.7.3：g++ -Wall -Wextra -std=c++0x factorable-neighbour.cpp

#include <iostream>
#include <vector>

using ints = std::vector<int>;

ints factor(int n, const ints& primes) {
  ints f(primes.size(), 0);
  for (int i = 0; i < primes.size(); ++i) {
    while (0< n && !(n % primes[i])) {
      n /= primes[i];
      ++f[i]; } }

  // append the "remainder"
  f.push_back(n);
  return f;
}

ints closest_factorable(int n, const ints& primes) {
  int d = 0;
  ints r;
  while (true) {
    r = factor(n + d, primes);
    if (r[r.size() - 1] == 1) { break; }
    ++d;
    r = factor(n - d, primes);
    if (r[r.size() - 1] == 1) { break; }
  }
  r.pop_back();
  return r; }

int main() {
  for (int i = 0; i < 30; ++i) {
    for (const auto& f : closest_factorable(i, {2, 3, 5, 7, 11})) {
      std::cout << f << " "; }
    std::cout << "\n"; }
}
于 2013-10-09T14:52:00.607 回答
0

Kissfft 有一个功能

int Kiss_fft_next_fast_size(int n)

返回下一个最大的 N，它是 2、3、5 的总和。

同样相关的是一个kf_factor 函数，它分解一个数字 n，首先拉出“好的”FFT 素数（例如，在 2 之前拉出 4）

于 2013-10-09T17:13:37.540 回答
0

我想你有一组（小）素数 S 和一个整数 n 并且你想知道 n 因子仅使用 S 中的数字。最简单的方法似乎如下：

P <- product of s in S
while P != 1 do
    P <- GCD(P, n)
    n <- n/P
return n == 1

您使用欧几里得算法计算 GCD。

想法如下：假设 S = {p1, p2, ... ,pk}。您可以将 n 唯一地写为

n = p1^n1 p2^n2 ... pk^nk * R

其中 R 与 pi 互质。你想知道R是否=1。

然后

GCD(n, P) = prod ( pi such that ni <> 0 ).

因此，n/p 将所有那些非零值 ni 减 1，使它们最终变为 0。最后只剩下 R。

例如：S = {2,3,5}，n = 5600 = 2^5*5^2*7。那么 P = 2*3*5 = 30。一个得到 GCD(n, p)=10=2*5。因此 n/GCD(n,p) = 560 = 2^4*5*7。

您现在又回到了同样的问题：您想知道 560 是否可以使用 S = {2,5} 分解，因此是循环。所以接下来的步骤是

  • GCD(560, 10) = 10。560/GCD = 56 = 2^3 * 7。
  • GCD(56, 10) = 2. 56/2 = 28 = 2^2 * 7
  • GCD(28, 2) = 2. 28/2 = 14 = 2 * 7
  • GCD(14, 2) = 2. 14/2 = 7
  • GCD(7, 2) = 1 使得 R = 7 ！如果 FALSE，您的答案。
于 2013-10-09T14:09:07.823 回答