Goldbach, R - rextester

Goldbach

Language: Layout:

library(gtools)

is.prime <- function(num) {
  if (num == 2) {
    TRUE
  } else if (any(num %% 2:(num-1) == 0)) {
    FALSE
  } else { 
    TRUE
  }
}

primesLessThan <- function(limit) {
  # Get prime numbers less than or equal to limit.
  d <- seq(2:(limit - 1))
  
  # Get only those divisors that are prime.
  d[sapply(d, is.prime) == TRUE]
}

findSums <- function(nums, target) {
  # Returns the combinations of nums that sum to the target.
  result <- NA

for (len in 1:5) {
    # Get all permutations of the numbers (repeat numbers allowed).
    sets <- permutations(length(nums), len, nums, repeats.allowed=T)
    
    # Calculate the sum of each set.
    totals <- apply(sets, 1, sum)
    
    # Find which set sums to our target.
    result <- sets[which(apply(sets, 1, sum) == target),]
    if (length(result) > 0) {
      break
    }
  }
  
  # Sort and filter the list to distinct numbers.
  unique(t(apply(result, 1, sort)))
}

goldbach <- function(target) {
  findSums(primesLessThan(target), target)
}

test <- c(11, 35, 111, 17, 199, 287, 53)
result <- sapply(test, goldbach)
print(result)

[ + ] Show input
Absolute running time: 1.46 sec, cpu time: 2.42 sec, memory peak: 65 Mb, absolute service time: 1,47 sec

[[1]] [,1] [,2] [,3] [1,] 2 2 7 [2,] 3 3 5 [[2]] [,1] [,2] [,3] [1,] 2 2 31 [2,] 3 3 29 [3,] 3 13 19 [4,] 5 7 23 [5,] 5 11 19 [6,] 5 13 17 [7,] 7 11 17 [8,] 11 11 13 [[3]] [,1] [,2] [1,] 2 109 [[4]] [,1] [,2] [,3] [1,] 2 2 13 [2,] 3 3 11 [3,] 3 7 7 [4,] 5 5 7 [[5]] [,1] [,2] [1,] 2 197 [[6]] [,1] [,2] [,3] [1,] 2 2 283 [2,] 3 3 281 [3,] 3 7 277 [4,] 3 13 271 [5,] 3 43 241 [6,] 3 61 223 [7,] 3 73 211 [8,] 3 103 181 [9,] 3 127 157 [10,] 5 5 277 [11,] 5 11 271 [12,] 5 13 269 [13,] 5 19 263 [14,] 5 31 251 [15,] 5 41 241 [16,] 5 43 239 [17,] 5 53 229 [18,] 5 59 223 [19,] 5 71 211 [20,] 5 83 199 [21,] 5 89 193 [22,] 5 101 181 [23,] 5 103 179 [24,] 5 109 173 [25,] 5 131 151 [26,] 7 11 269 [27,] 7 17 263 [28,] 7 23 257 [29,] 7 29 251 [30,] 7 41 239 [31,] 7 47 233 [32,] 7 53 227 [33,] 7 83 197 [34,] 7 89 191 [35,] 7 101 179 [36,] 7 107 173 [37,] 7 113 167 [38,] 7 131 149 [39,] 11 13 263 [40,] 11 19 257 [41,] 11 37 239 [42,] 11 43 233 [43,] 11 47 229 [44,] 11 53 223 [45,] 11 79 197 [46,] 11 83 193 [47,] 11 97 179 [48,] 11 103 173 [49,] 11 109 167 [50,] 11 113 163 [51,] 11 127 149 [52,] 11 137 139 [53,] 13 17 257 [54,] 13 23 251 [55,] 13 41 233 [56,] 13 47 227 [57,] 13 83 191 [58,] 13 101 173 [59,] 13 107 167 [60,] 13 137 137 [61,] 17 19 251 [62,] 17 29 241 [63,] 17 31 239 [64,] 17 37 233 [65,] 17 41 229 [66,] 17 43 227 [67,] 17 47 223 [68,] 17 59 211 [69,] 17 71 199 [70,] 17 73 197 [71,] 17 79 191 [72,] 17 89 181 [73,] 17 97 173 [74,] 17 103 167 [75,] 17 107 163 [76,] 17 113 157 [77,] 17 131 139 [78,] 19 29 239 [79,] 19 41 227 [80,] 19 71 197 [81,] 19 89 179 [82,] 19 101 167 [83,] 19 131 137 [84,] 23 23 241 [85,] 23 31 233 [86,] 23 37 227 [87,] 23 41 223 [88,] 23 53 211 [89,] 23 67 197 [90,] 23 71 193 [91,] 23 73 191 [92,] 23 83 181 [93,] 23 97 167 [94,] 23 101 163 [95,] 23 107 157 [96,] 23 113 151 [97,] 23 127 137 [98,] 29 29 229 [99,] 29 31 227 [100,] 29 47 211 [101,] 29 59 199 [102,] 29 61 197 [103,] 29 67 191 [104,] 29 79 179 [105,] 29 101 157 [106,] 29 107 151 [107,] 29 109 149 [108,] 29 127 131 [109,] 31 59 197 [110,] 31 83 173 [111,] 31 89 167 [112,] 31 107 149 [113,] 37 53 197 [114,] 37 59 191 [115,] 37 71 179 [116,] 37 83 167 [117,] 37 101 149 [118,] 37 113 137 [119,] 41 47 199 [120,] 41 53 193 [121,] 41 67 179 [122,] 41 73 173 [123,] 41 79 167 [124,] 41 83 163 [125,] 41 89 157 [126,] 41 97 149 [127,] 41 107 139 [128,] 41 109 137 [129,] 43 47 197 [130,] 43 53 191 [131,] 43 71 173 [132,] 43 107 137 [133,] 43 113 131 [134,] 47 47 193 [135,] 47 59 181 [136,] 47 61 179 [137,] 47 67 173 [138,] 47 73 167 [139,] 47 83 157 [140,] 47 89 151 [141,] 47 101 139 [142,] 47 103 137 [143,] 47 109 131 [144,] 47 113 127 [145,] 53 53 181 [146,] 53 61 173 [147,] 53 67 167 [148,] 53 71 163 [149,] 53 83 151 [150,] 53 97 137 [151,] 53 103 131 [152,] 53 107 127 [153,] 59 61 167 [154,] 59 71 157 [155,] 59 79 149 [156,] 59 89 139 [157,] 59 97 131 [158,] 59 101 127 [159,] 61 89 137 [160,] 61 113 113 [161,] 67 71 149 [162,] 67 83 137 [163,] 67 89 131 [164,] 67 107 113 [165,] 71 79 137 [166,] 71 89 127 [167,] 71 103 113 [168,] 71 107 109 [169,] 73 83 131 [170,] 73 101 113 [171,] 73 107 107 [172,] 79 101 107 [173,] 83 97 107 [174,] 83 101 103 [175,] 89 89 109 [176,] 89 97 101 [[7]] [,1] [,2] [,3] [1,] 3 3 47 [2,] 3 7 43 [3,] 3 13 37 [4,] 3 19 31 [5,] 5 5 43 [6,] 5 7 41 [7,] 5 11 37 [8,] 5 17 31 [9,] 5 19 29 [10,] 7 17 29 [11,] 7 23 23 [12,] 11 11 31 [13,] 11 13 29 [14,] 11 19 23 [15,] 13 17 23 [16,] 17 17 19