For this code challenge, you need to write a function that takes in an argument n and returns all the prime numbers that are less than or equal to n.

Rules:

• You cannot use any function that directly computes prime numbers for you.

• You cannot consult any list of prime numbers on the internet.

• You cannot load any external packages, but base R functions are allowed (unless you find one that directly computes prime numbers).

• You can’t bend the rules — you have to actually write a function to compute the prime numbers!

To win

• I’ll give you a number, you call your function on it, and you’ll need to tell me:

1. How many primes numbers are less than or equal to that number. Note: the first prime number is 2, so makes sure not to count 1.

2. What the largest prime number is that is less than or equal to the number I give you.

• You’ll have 10 seconds to be able to give me both of those.

Hint coming at the 5 minute mark…

Hint

The modulo operator takes one number and reports its remainder when it is divided by another number. This can be computed in R using the %% operator. For example,

5 %% 3
## [1] 2

Solution below…

# a function to check whether a number is prime or not
is_prime <- function(x) {
possibly_prime <- TRUE

# make i go from 2 to x-1
for (i in 2:(x-1)) {
# check if x mod i == 0
# if this condition holds, then x is not prime
if (x %% i == 0) {
possibly_prime <- FALSE
}
}

# handle x=2 separately
if (x==2) possibly_prime <- TRUE

# if we make it all the way to the end,
# and possibly_prime hasn't been set to FALSE,
# then x is a prime number; otherwise,
# is not a prime number
possibly_prime
}

# function to compute all prime numbers up to n
prime <- function(n) {
# list of possible prime numbers
candidates <- seq(2,n)

# apply the is_prime function to all of them
candidate_prime <- sapply(candidates, is_prime)

# return whichever ones were prime
candidates[candidate_prime]
}

# check that it works
prime(511)
##  [1]   2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67
## [20]  71  73  79  83  89  97 101 103 107 109 113 127 131 137 139 149 151 157 163
## [39] 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269
## [58] 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383
## [77] 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499
## [96] 503 509
length(prime(511))
## [1] 97
prime(423)
##  [1]   2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61  67
## [20]  71  73  79  83  89  97 101 103 107 109 113 127 131 137 139 149 151 157 163
## [39] 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269
## [58] 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383
## [77] 389 397 401 409 419 421
length(prime(423))
## [1] 82
prime(761)
##   [1]   2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61
##  [19]  67  71  73  79  83  89  97 101 103 107 109 113 127 131 137 139 149 151
##  [37] 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251
##  [55] 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359
##  [73] 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463
##  [91] 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593
## [109] 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701
## [127] 709 719 727 733 739 743 751 757 761
length(prime(761))
## [1] 135
prime(888)
##   [1]   2   3   5   7  11  13  17  19  23  29  31  37  41  43  47  53  59  61
##  [19]  67  71  73  79  83  89  97 101 103 107 109 113 127 131 137 139 149 151
##  [37] 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251
##  [55] 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359
##  [73] 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463
##  [91] 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593
## [109] 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701
## [127] 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827
## [145] 829 839 853 857 859 863 877 881 883 887
length(prime(888))
## [1] 154