\ 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  ( -- )
    FLAGS plimit 2/ 1 FILL
    3  EFLAG FLAGS DO
        I C@ 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/ 0 max +do
        flags i + c@ + loop ;

: solution ( -- u )
    1 \ counter, initialize with 1 to count 4=2*2
    -1 limit sqrt 2/ -do
        flags i + c@ 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.