用R( HackerEarth )求距离之间的最大素数差

Question

问题陈述:

在给定范围内找出素数之间的最大差。L，R

一些条件示例:

范围: 1，10 给定范围内质数之间的最大差为5。

差=7-2=5

范围: 5，5 只有一个不同的素数，所以最大的差是0。

范围:8，10 在给定范围内没有素数，因此给定范围的输出为-1。

范围:2-7 .这应该返回5. 7-2=5。

R码:

下面的R代码在中对我所传递的所有输入都很好。，但当我在hackerEarth Env中运行类似的代码时。获取误差

Input :

5
5 5
2 7
8 10
10 20
4 5

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

黑客地球输出：

在两个错误以下

1. Error In seq.int(2L * last.prime，n，last.prime)：在'by‘参数调用中出现错误符号: mapply -> ->筛子，此外:警告消息: In if (is.character(last.prime))seq.int <- get(兴趣，模式=“函数”)，get=parent.frame()：关闭未使用的连接3 (stdin)执行暂停

1. 时间限制超过

有没有更好的方法在不到一秒钟的时间内达到预期的效果。更正/建议受到高度赞赏。

Answer 1

是的，有。您的算法搜索间隔中的所有素数。让我们考虑一下1至1 000 000之间的范围。这意味着你将检查1000个数字是否为素数。这消耗了大量的存储资源，您不必要地将素数存储在1到1000之间。它也浪费了大量的计算资源，因为您不必要地计算了这1000次。

相反，在存储和计算效率方面，一种更有效的方法是：

通过从2开始的循环(因为1不是素数，不需要检查它是否为素数)和在第一个素数为found

• find时停止的，通过从完全向后开始的循环(总计，总计- 1，.)找到范围中的第一个素数。在找到最后一个素数，然后循环上面两个非常有效的循环之前，如果存在第一个素数和最后一个素数，您将知道第一个和最后一个素数，然后计算它们的差，否则返回一个默认值，如0

。

对不起，我没有为你写代码，但我不太懂R。