On May 9, 3:27 pm, an...@[EMAIL PROTECTED]
(Anton Ertl)
wrote:
> 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 =3D 3 =D7 5; 9 =3D 3 =D7 3; 12 =3D 2 =D7 2 =D7 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=3Dp1*p2, where p1<=3Dp2, 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<=3Dp2<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=3D2*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
PARI/gp
{
default( primelimit, 50000000 );
top =3D 10^8;
count =3D 0;
forprime( pr=3D2, sqrtint( top - 1 ),
count +=3D primepi( top \ pr ) - primepi( pr ) + 1 );
count
}
About 170ms on a slow, 800MHz laptop.
|
