That was another relatively easy one (or I would not have done it),
and it seems to be one of those that had not been solved by any of the
other registered Forth users (there is an advantage to us being so
few).
On a 3GHz Xeon 5160 takes 3.65s on gforth-fast and 3.32s on iForth. I
guess that the Sieve is running into the memory wall, that's why the
advantage of iForth is so small here.
As usual, you can download the program from
<http://www.complang.tuwien.ac.at/forth/programs/euler/187.fs>.
\ Problem 187:
\ A composite is a number containing at least two prime factors. For
\ example, 15 = 3 × 5; 9 = 3 × 3; 12 = 2 × 2 × 3.
\ There are ten composites below thirty containing precisely two, not
\ necessarily distinct, prime factors: 4, 6, 9, 10, 14, 15, 21, 22,
\ 25, 26.
\ How many composite integers, n < 10^8, have precisely two, not
\ necessarily distinct, prime factors?
\ Solution
\ I guess something smart can be done with prime-counting-only code,
\ but here I am going for a simple solution: Essentially, the numbers
\ we seek are of the form n=p1*p2, where p1<=p2, p1<sqrt(limit),
\ n<limit, p1 and p2 prime. I count them by generating the primes up
\ to sqrt(limit), then for each such prime p1 count the primes p2 with
\ p1<=p2<limit/p1. Since I'm lazy, I generate the primes up to
\ limit/2 and use them for counting.
\ As I said, I'm lazy, so I'll just adapt the Byte Sieve, as bad as it
\ may be.
\ If you use an ANS Forth system other than Gforth, get
\ <http://www.complang.tuwien.ac.at/forth/compat.zip>
and uncomment this:
\ s" compat/loops.fs" included
\ s" compat/anslocal.fs" included
100000000 constant limit
limit 2/ constant plimit \ a little more than needed
plimit 2/ allocate throw constant flags
FLAGS plimit 2/ + CONSTANT EFLAG
: PRIMES ( -- n )
FLAGS plimit 2/ 1 FILL
3 EFLAG FLAGS DO
I C@[EMAIL PROTECTED]
IF
DUP I + DUP EFLAG < IF
EFLAG SWAP DO
0 I C!
DUP +LOOP
ELSE
DROP THEN
THEN
2 + LOOP
DROP ;
: sqrt ( n1 -- n2 )
s>d d>f fsqrt f>d drop ;
: count-p2 { n1 -- n2 }
0 limit 1- n1 / 3 - 2/ 1+ n1 3 - 2/ +do
flags i + c@[EMAIL PROTECTED]
+ loop ;
: solution ( -- u )
1 \ counter, initialize with 1 to count 4=2*2
-1 limit sqrt 2/ -do
flags i + c@[EMAIL PROTECTED]
if
i 2* 3 + count-p2 + then
1 -loop
2 count-p2 + ;
primes solution . cr
\ You can speed this up by a little by remembering what COUNT-P2
\ produced last time, and only actually counting the primes that were
\ not counted last time, but I am too lazy for that. Besides, the
\ speedup is only small, because PRIMES takes most of the execution
\ time already (3.14s out of 3.65s on a 3GHz Xeon 5160 with
\ gforth-fast); strange, I would have expected SOLUTION to take a
\ similar amount of time.
--
M. Anton Ertl http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
New standard: http://www.forth200x.org/forth200x.html
EuroForth 2008:
http://www.complang.tuwien.ac.at/anton/euroforth/ef08.html
|
