Sequence of primes by trial division: Difference between revisions

 

 

 

 

=={{header|Ada}}==

Use the generic function Prime_Numbers.Is_Prime, as specified in [[Prime decomposition#Ada]]. The program reads two numbers A and B from the command line and prints all primes between A and B (inclusive).

 

 

procedure Sequence_Of_Primes is

end if;

end loop;

 

{{out}}

<pre>>./sequence_of_primes 50 99

53 59 61 67 71 73 79 83 89 97</pre>

 

=={{header|ATS}}==

// Lazy-evaluation:

// sieve for primes

end // end of [main0]

 

 

=={{header|D}}==

{{trans|Haskell}}

This is a quite inefficient prime generator.

std.numeric, std.concurrency;

 

.take(20)

.writeln;

{{out}}

<pre>[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]</pre>

 

=={{header|Go}}==

An unbounded cascading filtering method using channels, adapted from the classic concurrent prime sieve example in the "Try Go" window at http://golang.org/, improved by postponing the initiation of the filtering by a prime until the prime's square is seen in the input.

import "fmt"

func NumsFromBy(from int, by int, ch chan<- int) {

for i := from; ; i+=by {

}

}

func Filter(in <-chan int, out chan<- int, prime int) {

for {

}

}

func Sieve(out chan<- int) {

out <- 3

q := 9

ps := make(chan int)

go Sieve(ps) // separate primes supply

nums := make(chan int)

go NumsFromBy(5,2,nums) // end of setup

out <- n // n is prime

} else {

nums = ch1

}

}

}

 

func main() {

ch := make(chan int)

fmt.Print("First twenty:")

for i := 0; i < 20; i++ {

}

fmt.Println()

{{out}}

<pre>

</pre>

A simple iterative method, also unbounded and starting with 2.

 

import "fmt"

}

fmt.Println()

{{out}}

<pre>

 

=={{header|Haskell}}==

 

 

 

 

 

 

===Sieve by trial division===

where

sieve (p:xs) = p : sieve [x | x <- xs, rem x p /= 0]

-- map head

 

===Bounded sieve by trial division===

Bounded formulation has normal trial division complexity, because it can stop early via an explicit guard:

where

sieve (p:xs) | p*p > m = p : xs

| otherwise = p : sieve [x | x <- xs, rem x p /= 0]

 

===Postponed sieve by trial division===

To make it unbounded, the guard cannot be simply discarded. The firing up of a filter by a prime should be ''postponed'' until its ''square'' is seen amongst the candidates (so a bigger chunk of input numbers are taken straight away as primes, between each opening up of a new filter, instead of just one head element in the non-postponed algorithm):

 

===Segmented Generate and Test===

Explicating the run-time list of ''filters'' (created implicitly by the sieves above) as a list of ''factors to test by'' on each segment between the consecutive squares of primes (so that no testing is done prematurely), and rearranging to avoid recalculations, leads to the following:

 

primesST = 2 : 3 : sieve 5 9 (drop 2 primesST) (inits $ tail primesST)

where

sieve x q ps (fs:ft) = filter (\y-> all ((/=0).rem y) fs) [x,x+2..q-2]

<code>inits</code> makes a stream of (progressively growing) prefixes of an input stream, starting with an empty prefix, here making the <code>fs</code> parameter to get a sequence of values <code>[], [3], [3,5], ...</code>.

 

 

Implementation:

try=. i.&.(p:inv) %: >./ y

candidate=. (y>1)*y=<.y

y #~ candidate*(y e.try) = +/ 0= try|/ y

 

Example use:

 

 

Note that this is a filter - it selects values from its argument which are prime. If no suitable values are found the resulting sequence of primes will be empty.

 

 

{{out}}

 

=={{header|Racket}}==

This example uses infinite lists (streams) to implement a sieve algorithm that produces all prime numbers.

 

(define nats (cons 1 (map add1 nats)))

(define (sift n l) (filter (λ(x) (not (zero? (modulo x n)))) l))

(define (sieve l) (cons (first l) (sieve (sift (first l) (rest l)))))

(define primes (sieve (rest nats)))

 

==== Optimized with postponed processing ====

Since a prime's multiples that count start from its square, we should only add them when we reach that square.

 

(define nats (cons 1 (map add1 nats)))

(define (sift n l) (filter (λ(x) (not (zero? (modulo x n)))) l))

(λ(t) (sieve (sift (car ps) t) (cdr ps))))))

(define primes (sieve (cdr nats) primes))

 

=== Using threads and channels ===

Same algorithm as above, but now using threads and channels to produce a channel of all prime numbers (similar to newsqueak). The macro at the top is a convenient wrapper around definitions of channels using a thread that feeds them.

 

(define-syntax (define-thread-loop stx)

(syntax-case stx ()

(let ([x (channel-get c)]) (out! x) (set! c (sift x c))))

(define primes (let ([ns (nats)]) (channel-get ns) (sieve ns)))

 

=== Using generators ===

Yet another variation of the same algorithm as above, this time using generators.

 

(require racket/generator)

(define nats (generator () (for ([i (in-naturals 1)]) (yield i))))

(generator () (let loop ([g g]) (let ([x (g)]) (yield x) (loop (sift x g))))))

(define primes (begin (nats) (sieve nats)))

 

=={{header|REXX}}==

===somewhat optimized===

This is an open-ended approach and it's a simple implementation and could be optimized more with some easy programming.

<pre>

2

 

===more optimized===

 

=={{header|Ruby}}==

The Prime class in the standard library has several Prime generators. In some methods it can be specified which generator will be used. The generator can be used on it's own:

 

pg = Prime::TrialDivisionGenerator.new

p pg.take(10) # => [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

 

=={{header|Scala}}==

===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'''.

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)

{{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|Tcl}}==

As we're generating a sequence of primes, we can use that sequence of primes to describe what we're filtering against.

proc havePrime n {

global primes

}

}

{{out}}

<pre>

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

</pre>