Euler Problem 7 – 10001st prime

10001st prime

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10 001st prime number?

I had written the code for this function. However, I faced various computational problems while

solving this. Tried various approaches but calculating 10 001 st prime number require lot of memory which wasn’t available with me. Hence, reduced the problem to finding 1000 th prime number.

In this problem, we are using the is_prime function which we had used previously which states result as True or False depending on whether a particular number is prime or not.

is_prime = function(num) {
  flag = 0
  if (num %% 2 == 0) return(FALSE)
  if (num == 3 | num == 5) return(TRUE)
  for (i in seq(3, floor(num/2), by=2)) {
    if (num %% i == 0) {
      flag = 1
      return(FALSE)
    }
  }
  return(TRUE)
}

get_nth_Prime = function(n) {
  num_list = (2:4000) * 2 -1
  boolean_list = which(sapply(num_list, is_prime))
  num_list[boolean_list[n-1]]
}

We generate an odd-valued sequence from 3 to 8000 (as 1000th prime number is 7919). For every number in that odd valued sequence we only save the numbers which are prime and then from those numbers we select  nth number.

get_nth_Prime(20)
[1] 71
get_nth_Prime(1000)
[1] 7919
get_nth_Prime(987)
[1] 7793

Checked the answers from this link .

I just googled the answer for this problem which gave me the result as 104743. So, it was not that big number as i was hoping it to be. Updated the function with

get_nth_Prime = function(n) {
  num_list = (2:55000) * 2 -1
  boolean_list = which(sapply(num_list, is_prime))
  num_list[boolean_list[n-1]]
}

And i was able to get the desired result.

get_nth_Prime(10001)
[1] 104743

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s