检查数字是否可分解为一组素数的算法

Question

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

非常感谢您的帮助。

Answer 1

总的来说，这看起来像是一个难题，尤其是找到下一个最大的整数来考虑你的素数集。但是，如果您的素数集不是太大，一种方法是通过获取日志将其转化为整数优化问题。以下是如何找到最小的数 > 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
>