我试图想出一个方法,它接受一个整数并返回一个布尔值来说明数字是否为素数,我不知道多少C; 有人会关心给我一些指示吗？
基本上,我会在C#中这样做:
static bool IsPrime(int number)
{
for (int i = 2; i < number; i++)
{
if (number % i == 0 && i != number)
return false;
}
return true;
}
这不是作业,我只是好奇.
INFINITE是这里的关键词.
我希望在primes()中使用它作为p.我相信这是Haskell中的内置函数.
所以,答案不能像"Just do a Sieve"那样天真.
首先,您不知道将消耗多少连续素数.好吧,假设你可以一次编制100个.您是否会使用相同的Sieve方法以及素数公式的频率？
我更喜欢非并发方法.
感谢您阅读(和写作;))!
我一直在努力解决Clojure中的Project Euler问题,以便变得更好,而且我已经遇到了几次素数.我的问题是它只是花了太长时间.我希望有人可以帮我找到一种以Clojure-y方式做到这一点的有效方法.
当我拳头做到这一点时,我粗暴地强迫它.这很容易做到.但是计算10001个素数在Xeon 2.33GHz上用了2分钟,对规则来说太长了,一般来说太长了.这是算法:
(defn next-prime-slow
"Find the next prime number, checking against our already existing list"
([sofar guess]
(if (not-any? #(zero? (mod guess %)) sofar)
guess ; Then we have a prime
(recur sofar (+ guess 2))))) ; Try again
(defn find-primes-slow
"Finds prime numbers, slowly"
([]
(find-primes-slow 10001 [2 3])) ; How many we need, initial prime seeds
([needed sofar]
(if (<= needed (count sofar))
sofar ; Found enough, we're done
(recur needed (concat sofar [(next-prime-slow …我无法理解这段代码:
let
sieve (p:xs) = p : sieve (filter (\ x -> x `mod` p /= 0) xs)
in sieve [2 .. ]
有人可以为我分手吗？我知道它有递归,但这就是问题我无法理解这个例子中的递归是如何工作的.
我正在学习Erlang.作为练习,我选择了生成素数的Eratosthenes算法.这是我的代码:
-module(seed2).
-export([get/1]).
get(N) -> WorkList = lists:duplicate(N, empty),
get(2, N, WorkList, []).
get(thats_the_end, _N, _WorkList, ResultList) -> lists:reverse(ResultList);
get(CurrentPrime, N, WorkList, ResultList) -> ModWorkList = markAsPrime(CurrentPrime, N, WorkList),
NextPrime = findNextPrime(CurrentPrime + 1, N, WorkList),
get(NextPrime, N, ModWorkList, [CurrentPrime|ResultList]).
markAsPrime(CurrentPrime, N, WorkList) when CurrentPrime =< N -> WorkListMod = replace(CurrentPrime, WorkList, prime),
markAllMultiples(CurrentPrime, N, 2*CurrentPrime, WorkListMod).
markAllMultiples(_ThePrime, N, TheCurentMark, WorkList) when TheCurentMark > N -> WorkList;
markAllMultiples(ThePrime, N, TheCurrentMark, WorkList) -> WorkListMod = replace(TheCurrentMark, WorkList, marked),
markAllMultiples(ThePrime, …在找到第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))
从我所看到的,这不会导致这种类似递归的方式.这是一个很好的方法吗,或者你知道更好的方法吗？
performance primes scala out-of-memory sieve-of-eratosthenes
在Haskell中,我在Rosetta Code页面上找到了三个简单的Eratosthenes Sieve实现.
现在我的问题是,应该在哪些情况下使用哪一个？
纠正我的初步推理也会有所帮助:
我假设列表一是Haskeller中最惯用且易于阅读的.但是这是正确的吗？我想知道它是否遇到了与另一个基于列表的筛子相同的问题,然后我学会了实际上没有实现算法:(
编辑:这里显示的是我知道有问题的基于列表的筛子,而不是来自RosettaCode的筛子,我贴在底部)
primes = sieve [2..] where
sieve (p:x) = p : sieve [ n | n <- x, n `mod` p > 0 ]
在性能方面,不可变阵列似乎是赢家.随着上限m的2000000,这些时间是约:
所以我选择Array来表现.
当然,Mutable Array也很容易推理,因为我有更迫切的语言背景.我不知道为什么我会选择这个,如果我在Haskell编码,因为它既慢于其他人,也不是非惯用的.
此处复制的代码仅供参考:
列表:
primesTo m = 2 : eratos [3,5..m] where
eratos (p : xs) | p*p>m = p : xs
| True = p : eratos (xs `minus` [p*p, p*p+2*p..])
minus a@(x:xs) b@(y:ys) = case compare x …