prime number function with nested loop in R gives incorrect results-CodePudding

I need to make a function that returns a vector of all prime numbers from 3 to n. I know there are easier ways to make a function determining if a number is prime or not, but I was specifically asked to use 2 loop. my function:

prime.numbers = function(n= 100){
  l=c()
  for (i in 3:n){
    for (j in 2:ceiling(sqrt(i))){
      if ((i %% j )== 0) {
        break      }
      else{ l= append(l,i)}
    }  }
  return(l)}

prime.numbers()

for the example of n = 100 I got:

  [1]  3  5  5  7  7  9 11 11 11 13 13 13 15 17 17 17 17 19 19 19 19 21 23 23 23 23
 [27] 25 25 25 27 29 29 29 29 29 31 31 31 31 31 33 35 35 35 37 37 37 37 37 37 39 41
 [53] 41 41 41 41 41 43 43 43 43 43 43 45 47 47 47 47 47 47 49 49 49 49 49 51 53 53
 [79] 53 53 53 53 53 55 55 55 57 59 59 59 59 59 59 59 61 61 61 61 61 61 61 63 65 65
[105] 65 67 67 67 67 67 67 67 67 69 71 71 71 71 71 71 71 71 73 73 73 73 73 73 73 73
[131] 75 77 77 77 77 77 79 79 79 79 79 79 79 79 81 83 83 83 83 83 83 83 83 83 85 85
[157] 85 87 89 89 89 89 89 89 89 89 89 91 91 91 91 91 93 95 95 95 97 97 97 97 97 97
[183] 97 97 97 99

which is obviously wrong. I get an increasing number of the same value for some reason, and some of it isn't even a prime number.

can anyone help me understand what I'm doing wrong? thank you

CodePudding user response：

Don't append the number within your second for loop, do it as the result of a comparison after the j loop. The reason? For every number between 2 and ceiling(sqrt(i)), you are making the comparison, and for each of them; I believe you intend to do that only once per i, not per j.

Instead, move the append to the end of the first loop, and do another comparison before appending it.

prime_number <- function(n = 100) {
  l = c()
  for (i in 3:n){
    for (j in 2:ceiling(sqrt(i))){
      if ((i %% j) == 0) break
    }
    if ((i %% j) != 0) { l = append(l,i); }
  }
  l
}
prime_number()
#  [1]  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

CodePudding user response：

You can set a toggle prime <- TRUE. If a composite(non-prime) number is encountered, switch it off as prime <- FALSE and break. In the end of the inner loop, if the prime toggle is still TRUE, append the number i to the output vector.

prime.numbers = function(n = 100) {
  l <- c()
  for (i in 3:n) {
    prime <- TRUE
    for (j in 2:ceiling(sqrt(i))) {
      if (i %% j == 0) { prime <- FALSE; break }
    }
    if(prime) l <- append(l, i)
  }
  return(l)
}

prime.numbers()
# [1]  3  5  7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

CodePudding user response：

Well, for starters, you should append the number to the list after the nested for, only once, when you verified that it's not divisible for any number.

Your code instead appends it every time it founds a divisor that does not return 0 for i %% j, which could happen more than once for a given number, even if other checks fail. This sums up your code symptoms.