Something like this works:
: multiple-of? ( x y -- ? )
{ [ = not ] [ mod 0 = ] } 2&& ;
: find-primes-til ( n -- seq )
[ iota ] [ 2 swap sqrt [a,b] ] bi [
'[ _ multiple-of? not ] filter
] each rest ;
10000 find-primes-til
You only need to filter up to the square root of the highest number
you want to test. Here we're testing each element of the range 2..n
by filtering the sequence with your multiple-of? word. Each iteration
outputs a new sequence that the next iteration operates on. Calling
rest at the end removes the integer 1 from the list, since it's not
prime. 2&& is a short-circuit combinator, which marginally speeds
things up by skipping the second quotation as soon as the first
returns false.
There are ways to speed up this algorithm, like starting with two,
filtering out the potential primes list, and then taking the next
prime in that list after two (3) and filtering on that. Then take the
next number (5), since (4) was filtered out by the two. Then (7)
since (6) was filtered by the (3)...etc..
Have fun,
Doug
On Sep 18, 2009, at 6:42 AM, Scott Brown wrote:
>
> I have started learning Factor and after trying out the
> palindrome tutorial, I am now trying to make a simple
> program for filtering out non-prime numbers from a list.
>
> I have made a word multiple-of? which returns true if
> x is a multiple of y.
>
> : multiple-of? ( x y -- ? ) [ = not ] [ mod 0 = ] 2bi and
> ;
>
> I would like to use it filter a sequence of numbers
> like the expression below, but looping through each of
> the numbers in the sequence to remove its multiples,
> leaving only prime numbers.
>
> { 2 3 4 5 6 7 8 9 10 } [ 2 multiple-of? not ] filter
>
> Is there some loop or combinator that I could use to do
> this in Factor?
>
>
> --------------------------------------
> Thanks 10 years! Yahoo! Shopping and Yahoo! Auctions
> http://pr.mail.yahoo.co.jp/ec10years/
>
> ------------------------------------------------------------------------------
> Come build with us! The BlackBerry® Developer Conference in SF, CA
> is the only developer event you need to attend this year. Jumpstart
> your
> developing skills, take BlackBerry mobile applications to market and
> stay
> ahead of the curve. Join us from November 9-12, 2009. Register
> now!
> http://p.sf.net/sfu/devconf
> _______________________________________________
> Factor-talk mailing list
> [email protected]
> https://lists.sourceforge.net/lists/listinfo/factor-talk
------------------------------------------------------------------------------
Come build with us! The BlackBerry® Developer Conference in SF, CA
is the only developer event you need to attend this year. Jumpstart your
developing skills, take BlackBerry mobile applications to market and stay
ahead of the curve. Join us from November 9-12, 2009. Register now!
http://p.sf.net/sfu/devconf
_______________________________________________
Factor-talk mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/factor-talk
