Primality by trial division: Difference between revisions
Content deleted Content added
→{{header|Racket}}: move Racket sieves here from Sieve of Eratosthenes, as per discussion on the talk page of SoE; use standard whitespace formatting |
→{{header|Scala}}: move TD-sieve from SoE as per talk page discussion there |
||
| Line 2,207: | Line 2,207: | ||
assert(isPrime(214748357)) |
assert(isPrime(214748357)) |
||
assert(!isPrime(Int.MaxValue - 1))</lang> |
assert(!isPrime(Int.MaxValue - 1))</lang> |
||
===Odds-Only "infinite" primes generator using Streams and Co-Inductive Streams=== |
|||
Using Streams, [http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf the "unfaithful sieve"], i.e. '''sub-optimal trial division sieve. Not a sieve of Eratosthenes'''. |
|||
<lang scala>def sieve(nums: Stream[Int]): Stream[Int] = |
|||
Stream.cons(nums.head, sieve((nums.tail).filter(_ % nums.head != 0))) |
|||
val primes = 2 #:: sieve(Stream.from(3, 2)) |
|||
println(primes take 10 toList) // //List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29) |
|||
println(primes takeWhile (_ < 30) toList) //List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)</lang> |
|||
{{out}}Both println statements give the same results: |
|||
<pre>List(2, 3, 5, 7, 11, 13, 17, 19, 23, 29)</pre> |
|||
The above code is extremely inefficient for larger ranges, both because it tests for primality using computationally expensive divide (modulo) operations and because it sets up deferred tests for division by all of the primes up to each prime candidate, meaning that it has approximately a square law computational complexity with range. |
|||
=={{header|Scheme}}== |
=={{header|Scheme}}== |
||