Search code examples
algorithmfftprime-factoring

Algorithm for checking if number is factorable into a set of prime numbers

I was wondering if there is an algorithm that checks wether a given number is factorable into a set of prime numbers and if no give out the nearest number. The problem comes always up when I use the FFT.

Thanks a lot for your help guys.

Solution

  • In general this looks like a hard problem, particularly finding the next largest integer that factors into your set of primes. However, if your set of primes isn't too big, one approach would be to turn this into an integer optimization problem by taking the logs. Here is how to find the smallest number > n that factors into a set of primes 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

    The x_i will give you the exponents for the primes. Here is an implementation in R using lpSolve:

    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
>

    Using big integers, this works pretty well even for large numbers:

    > 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
>