相关疑难解决方法(0)

Eratosthenes的Sieve可以在Haskell中非常巧妙地实现,使用懒惰生成无限列表,然后从尾部删除列表头部的所有倍数:

primes :: [Int]
primes = sieve [2..]
sieve (x:xs) = x : sieve [y | y <- xs, y `mod` x > 0]

我正在尝试学习如何在Java 8中使用流,但我想出是否有一种方法可以在Java中实现与上面的Haskell代码相同的结果.如果我将Haskell惰性列表视为等同于Java流,似乎我需要使用以2为首的流并生成一个删除了所有2的倍数的新流,然后获取该流并生成所有流的新流删除3的倍数,并...

我不知道如何继续.

有没有办法做到这一点,或者当我试图将Java流视为与Haskell列表相当时,我是在欺骗自己？

这是Haskell中定点组合器的通常定义:

fix :: (a -> a) -> a
fix f = let x = f x in x

在https://wiki.haskell.org/Prime_numbers上,他们定义了一个不同的定点组合子:

_Y   :: (t -> t) -> t
_Y g = g (_Y g)                -- multistage, non-sharing,  g (g (g (g ...)))
    -- g (let x = g x in x)    -- two g stages, sharing

_Y是一个非共享的固定点组合器,在这里安排递归"伸缩"多级素数生产(生产者塔).

这到底是什么意思？在这种情况下,"共享"与"非共享"是什么？有_Y什么不同fix？

在找到第10,001个素数时,我的内存耗尽.

object Euler0007 {
  def from(n: Int): Stream[Int] = n #:: from(n + 1)
  def sieve(s: Stream[Int]): Stream[Int] = s.head #:: sieve(s.filter(_ % s.head != 0))
  def primes = sieve(from(2))
  def main(args: Array[String]): Unit = {
    println(primes(10001))
  }
}

这是因为在每次"迭代"(这是这个上下文中的正确术语吗？)之后primes,我增加要调用的函数堆栈以使下一个元素一个接一个？

我在网上找到的一个解决方案是不使用迭代解决方案(我想避免进入函数式编程/惯用scala),这就是问题7(问题7):

lazy val ps: Stream[Int] = 2 #:: Stream.from(3).filter(i => ps.takeWhile(j => j * j <= i).forall(i % _ > 0))

从我所看到的,这不会导致这种类似递归的方式.这是一个很好的方法吗,或者你知道更好的方法吗？

我读了这篇关于这个算法的F#版本的帖子.我发现它非常优雅,并试图结合一些答案的想法.

虽然我对它进行了优化以减少检查(仅检查6左右的数字)并省去不必要的缓存,但仍然很慢.计算10,000 ^次素数已经超过5分钟.使用命令式方法,我可以在更长的时间内测试所有31位整数.

所以我的问题是,如果我遗漏了使这一切变得如此缓慢的事情.例如,在另一篇文章中有人猜测LazyList可能会使用锁定.有没有人有想法？

由于StackOverflow的规则说不要将新问题作为答案发布,我觉得我必须为此开始一个新主题.

这是代码:

#r "FSharp.PowerPack.dll"

open Microsoft.FSharp.Collections

let squareLimit = System.Int32.MaxValue |> float32 |> sqrt |> int

let around6 = LazyList.unfold (fun (candidate, (plus, next)) -> 
        if candidate > System.Int32.MaxValue - plus then
            None
        else
            Some(candidate, (candidate + plus, (next, plus)))
    ) (5, (2, 4))

let (|SeqCons|SeqNil|) s =
    if Seq.isEmpty s then SeqNil
    else SeqCons(Seq.head s, Seq.skip 1 s)

let rec lazyDifference l1 l2 =
    if Seq.isEmpty l2 then …

我的阶乘函数似乎适用于 1 到 6 之间的数字，但不适用于比 6 大得多的数字，例如以 21 开头！结果是否定的。

我不明白为什么。这是我的功能：

factorial :: Int -> Int
factorial 0 = 1
factorial 1 = 1
factorial num = num * factorial( num - 1)

这是我的二项式系数函数，它调用我的阶乘函数（也许问题来自这个？）：

binomialCoef :: Int -> Int -> Int
binomialCoef n 1 = n
binomialCoef n k = factorial n `div` 
                        ((factorial k) * factorial (n - k))

我有一个问题要打印一百万个素数.我已经为此编写了一个java程序.它目前需要1.5分钟来计算它.我认为我的解决方案效率不高.我使用了以下算法:

• 最初将1 2 3添加到主要列表中
• 计算要检查的数字的最后一位数
• 检查数字是0,2或4还是6或8,然后跳过该数字
• 否则计算数字的平方根..
• 试图将从2开始的数字除以数字的平方根
• 如果数字是可分的,则跳过该数字,否则将其添加到主要列表中

我也读过其他几个解决方案,但我没有找到一个好的答案.请在理想情况下建议最小化计算时间,以及使算法更有效所需的更改.

我对如何解决这个问题有点困惑。我需要所有素数才能返回 true。如果不返回 false——我看到我的逻辑包括 2 并且返回 0，所以它自动返回 false，因为 2 余数为 0。

  

  function isPrime(num, div = 2) {
      // BASE CASE: 
     
      if(num <= div ) return false; // IF num less than OR equal to  2 RETURN false 
      
      // IF num MOD has a remainder of zero   
         
      if(num % 2 === 0) return false  // RETURN false 
      
      return true; // RETURN true
     
      // RECURSIVE CALL:

      return isPrime(num)
    }

    console.log(isPrime(1)); //-> false
    console.log(isPrime(2)); //-> true
    console.log(isPrime(3)); //-> true
    console.log(isPrime(4)); //-> false

我是Haskell编程的新手,无法理解下面的列表理解是如何扩展的.

primes = sieve [2..] 
sieve (p:xs) = p : sieve [x | x <-xs, x `mod` p /= 0]

有人可以纠正sieve扩展如何工作:

• 因为我们是模式匹配sieve,p会关联2和x来自[3..].
• 接下来,在列表理解中x<-3,但是3当没有短路时我们怎样才能调用筛子.

其他我不明白的是递归如何在这里起作用.

我认为很清楚,如果能够在前几个数字的情况下一次扩展上述一步,那就说直到5.