Euler 193 is about counting square free numbers.
Find all numbers not divisable by a square under 2^50.
This looks like sieving for primes, but instead of
scratching multiples of primes, squares are discarded.

However the problem doesn't admit of a straightforward
sieving solution because the 2^50 is too great (10^15).

I have adapted benchpin.frt and it returns the literature
values up till 10^10. So I have a working program!

This takes 4 minutes on a heavy duty AMD.
I'm out of steam. I can't understand why this
problem can be easier than counting primes. My program
will run a couple of thousand days on this problem!

The rule is that an Euler program should take at most a minute.
42 people have solved it.

Groetjes Albert

mhx@iae.nl (Marcel Hendrix) writes Re: [SPOILER] Re: Euler problem #187

Never forget the old but nonetheless excellent work of others (in this
case Albert van der Horst).

-marcel

-- --------------------------------------------------------------------------------------
INCLUDE ../benchmar/benchpin.frt \ PI(N2) ( n1 -- n2 ) counts all primes below n1

(*
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?

( sorry about that )

Albert van der Horst writes Re: euler 193, I have a solution but too slow.
[..]

Aren't you overlooking the obvious?
When the square of a prime is < 2^50, the prime is < 2^25.
This means that an array of 8 * 2^25 bytes (240 MB) can be
used to see if n is divisible by the square of a prime (which
is a 64 bit number). This looks rather straightforward, so I
must be overlooking something :-)

Marcel Hendrix wrote:

Good reference! Te solution is obvious now.

-- Charles

cac wrote:

Hmmm. Obvious, but wrong. Time to hit the books again.

-- Charles

Albert van der Horst wrote:

Hm, I'm not sure if this really is a prime marking equivalent. E.g. look at
the task: 4 and 9 are not square-free, but 2 and 3 primes. At least you
need only find all primes up to 2^25 (16MB sieve, please use an optimized
sieve that stops marking at sqrt(N), and remember to insert the 2 in the
list).

While you walk through the list of primes up to 2^25, you can calculate how
many numbers up to 2^50 it takes out as not squarefree, but you need to
calculate how many doubles you had. This can be done by accumulation:

4 takes out 1/4 of the numbers, keep 1/4 in mind.

9 takes out 1/9 of the numbers, but 1/4 of those (1/36) have already been
taken out by 4, so you remember 1/4+1/9*(1-1/4).

In article ,
Bernd Paysan wrote:

Albert van der Horst wrote:

There's no recursion at all. You keep track of how many numbers have been
taken out by the primes you found so far, and add what's being taken out
*in addition* by the new prime you found, i.e. acc+=(1-acc)*1/prime

2 takes out 1/2 of the numbers, acc=0, so acc+=1*1/2=1/2.
3 takes out 1/3 of the numbers, acc=1/2, so acc+=1/2*1/3=1/6, so acc=2/3.
5 takes out 1/5 of the numbers, acc=2/3, so acc+=1/3*1/5=1/15, so acc=11/15.