Find maximum Prime Difference between Range using R ( HackerEarth )

Question

PROBLEM STATEMENT :

Find maximum difference between the prime numbers in the given range. [L,R]

SOME CONDITION EXAMPLE :

Range: [ 1, 10 ] The maximum difference between the prime numbers in the given range is 5.

Difference = 7 - 2 = 5

Range: [ 5, 5 ] There is only one distinct prime number so the maximum difference would be 0.

Range: [ 8 , 10 ] There is no prime number in the given range so the output for the given range would be -1.

Range: [ 2 - 7 ] . This should return 5. [ 7 - 2 ] = 5

R Code :

The below R code works fine in R studio for all input I have passed. But when I ran the similar code in hackerEarth Env. Getting Errors

input <- readLines(stdin(), n=6)
total <- as.numeric(input[1]) 
val <- 1:total
for (i in 1:total )  
 {
   val[i] <- input[i+1]

} 

df <- data.frame(val) 
df <- str_split_fixed(df$val, " ", 2)
lf <- data.frame(l=df[,1],r=df[,2])
dat <- as.data.frame(sapply(lf, as.numeric))

#Find Prime Sequence
sieve <- function(n)
{
   n <- as.integer(n)
   if(n > 1e6) stop("n too large")
   primes <- rep(TRUE, n)
   primes[1] <- FALSE
   last.prime <- 2L
   for(i in last.prime:floor(sqrt(n)))
   {
      primes[seq.int(2L*last.prime, n, last.prime)] <- FALSE
      last.prime <- last.prime + min(which(primes[(last.prime+1):n]))
   }
   which(primes)
}
#Find Next Prime
np <- function(x){
 if (x==1L | x==2L) {return(2L)}
 else { 
  temp <- x+1
  test <- 2:x
  while( any( (temp %% test) == 0 ) ){
    temp <- temp+1
  }
  temp
} }
# Pass LR
prime <- function(l,r)
{

    if (l==r) { return(0L) }    
    else if( (r - np(l)) == 0 ) { return(0L) }  
    else if( max(sieve(r)) - np(l) < 0)  { return(-1L) }    
    else { return(max(sieve(r)) - np(l)) }  

}


cat(mapply(prime,dat$l,dat$r),sep='\n')

R studio Output :
0
5
-1
8
0

Hacker Earth Output :

Getting below two Errors

Error in seq.int(2L * last.prime, n, last.prime) : wrong sign in 'by' argument Calls: mapply -> -> sieve In addition: Warning message: In if (is.character(fun)) fun <- get(fun, mode = "function", envir = parent.frame()) : closing unused connection 3 (stdin) Execution halted
Time Limit Exceeded

Is there a better way to achieve the desired results in less than a second. Corrections/Suggestions are highly appreciated

If you want to speed up, you should use sieve algorithm. An implementation can be referred to is https://stackoverflow.com/a/3790309/12158757 — ThomasIsCoding, Jun 03 '21 at 16:01

score 1 · Accepted Answer · answered Jun 03 '21 at 10:52

Yes, there is. Your algorithm searches for all primes in the interval. Let's consider the range between 1 and 1 000 000. That means that you will check for 1 000 000 numbers whether they are prime. That uses up a lot of storage resources, you unnecessarily store the primes between 1 and 1 000 000. It also wastes a lot of computational resources, since you unnecessarily compute this 1 000 000 times.

Instead, a much more efficient way to do this both in terms of storage and computation efficiency is to:

find the first prime in the range via a loop starting from 2 (because 1 is not a prime, no need for check whether it's prime) and which stops when the first prime is found
find the last prime in the range via a loop starting from total backwards (total, total - 1, ...) until you find the last prime and then the loop stops
with the two very efficient loops above, you will know the first and the last prime if they exist
if there is a first and a last prime, then compute their difference, otherwise return a default value, like 0

Excuse me for not writing code for you, but I'm not fluent in R.

Find maximum Prime Difference between Range using R ( HackerEarth )

1 Answers1