Counting primes in Factor

Tagged as en, factor

Written on 2011-01-12

Last week Programming Praxis proposed to write two functions:

• prime-counting(n) function, that returns the number of primes to n
• nth-prime(n) function, that returns the nth prime number

A day before Samuel Tardieu wrote an article about Positional factoring which included information about the math.primes vocabulary in Factor. He also included a solution on J which is also used to provide a solution to the Programming Praxis problem (see the first comment). So I decided to write an implementation in Factor, which is a very easy task.

Counting primes

primes-upto takes a number and returns a sequence of prime numbers up to that one, so we just need to count the sequence length to get intended result:

USING: sequences math.primes ;
: prime-counting ( x -- y )
    primes-upto length ;

Testing it, works as expected:

( scratchpad ) 100 prime-counting .
25
( scratchpad ) { 100 101 102 103 104 } [ prime-counting ] map .
{ 25 26 26 27 27 }

Nth prime

This problem is a bit more complex, yet Factor provides a great solution in math.primes.lists making use of Lazy lists: lprimes provides an infinite stream of prime numbers, so we just need to take as many prime numbers as needed and return the last:

USING: sequences math.primes lists lists.lazy math.primes.lists ;
: nth-prime ( x -- y )
    lprimes ltake list>array last ;

Testing it, works as expected:

( scratchpad ) 25 nth-prime .
97
( scratchpad ) { 24 25 26 27 28 } [ nth-prime ] map .
{ 89 97 101 103 107 }

And that’s pretty much about it. Here you have the whole counting-primes vocabulary:

USING: sequences math.primes lists lists.lazy math.primes.lists ;
IN: counting-primes
: prime-counting ( x -- y )
    primes-upto length ;

: nth-prime ( x -- y )
    lprimes ltake list>array last ;

• ← Previous
• Next →