[seqfan] Eratothenes-like sieve for squarefree numbers

[Vladimir Shevelev]

For integers>=2: 
1) Remove even numbers, except for 2; the minimal not
 removed number is 3.
2) Recover the removed on step 1) multiples of 3 and remove other 
multiples of 3, except for 3 itself; the minimal not removed number is 5.
3) Recover the removed as a result of steps 1),2) multiples of 5 and remove other 
multiples of 5, except for 5 itself; the minimal not removed number is 6.
4) Recover the removed as a result of steps 1),2),3) multiples of 6 and remove other 
multiples of 6, except for 6 itself; the minimal not removed number is 7, etc.

Example 1. 30 removed on step 1) (multiples of 2), recovered on step 2)
 (multiples of 3), removed on step 3) (multiples of 5), recovered on step 4)
(multiples of 6), removed on step 6) (multiples of 10) and recovered on step
10) (multiples of 15). On step 18) (multiples of 30), 30 itself remains.
Example 2. 36  removed on step 1) (multiples of 2), recovered on step 2)
 (multiples of 3) and removed on step 4) (multiples of 6). Note that other 
proper divisors>1 of 36: 4,9,12,18 were removed before 36.

Proof. We use induction. Let before number n, as a result of the algorithm,
we have all squarefree numbers<n and none of other numbers.
 If n is squarefree, then the number of its proper divisors
 d>1 is even (it is 2^k - 2, where k is the number of its prime divisors), and,
 by the algorithm, it remains.  Otherwise, n is removed, since the number of 
its squarefree divisors>1 is odd (it is 2^k-1). 

Best regards
Vladimir