Advertisement
celestialgod

Fast method to fin prime factor

Nov 4th, 2015
213
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
R 1.21 KB | None | 0 0
  1.  
  2. findDivisor <- function(num){
  3.   p = vector('numeric', 1e5)
  4.   k = 1
  5.   step_p = 1e7
  6.   repeat{
  7.     s = min(k, num):min(num, k+step_p)
  8.     tmp = which(num %% s == 0)
  9.     if (length(tmp) > 0)
  10.     {
  11.       if (sum(p!=0)+length(tmp) > 1e5)
  12.         p = c(p, rep(0, 1e5))
  13.       p[(sum(p!=0)+1):(sum(p!=0)+length(tmp))] = s[tmp]
  14.     }
  15.     if (k > num)
  16.       break
  17.     k = k + step_p
  18.   }
  19.   unique(p[p!=0])
  20. }
  21.  
  22. primefactorFast <- function(num){
  23.   p <- findDivisor(num)
  24.   isPrime <- function(num){
  25.     return(length(findDivisor(num)) == 2)
  26.   }
  27.   p <- p[sapply(p, isPrime)]
  28.   e <- vector('numeric', length(p))
  29.   e_basic <- 1
  30.   step_e <- 5
  31.   subset_e <- 1:length(p)
  32.   repeat{
  33.     m = num %% sweep(matrix(replicate(step_e, p[subset_e]), length(p[subset_e])), 2,
  34.       e_basic:(e_basic + step_e - 1), '^') == 0
  35.     e[subset_e] = e[subset_e] + rowSums(m)
  36.     e_basic = e_basic + step_e
  37.     subset_e = which(apply(m,1,all))
  38.     if (is.null(subset_e) || (length(subset_e) == 0))
  39.       break
  40.   }
  41.   return(list('pfactor'=p, 'multi'=e))
  42. }
  43. testNum = 2^11*3^6*47
  44. log10(testNum) # [1]  7.846155
  45. st = proc.time()
  46. out = primefactorFast(testNum)
  47. proc.time() - st
  48. #   user  system elapsed
  49. #   5.74    0.78    6.52
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement