Gawk algorithm for finding numbers of k-almost primes
(Dave Robinson, Brisbane, 2004: http://daverobinson.id.au)
# Run with gawk -f
# Between any 2 numbers x and y find the number of numbers which are 1-factor (prime), 2-factor (semiprime),
# 3-factor, 4-factor or >4-factor
BEGIN{o="almostpno_out.txt" # File for output
x = 2
# Enter
required value or expression for x
y = 10^5
# Enter required value or expression
for y
for(a=x; a<=y; a++){
m1=0; m2=0; m3=0; m4=0 # m1-m4 are flags
for(b=2; b<=sqrt(a); b++){
if(a%b==0){c=a/b; m1=1; break}} # If a has factors, the first factor found (b) is prime; if no factors,
if(m1==0){f1++; continue}i # a is prime, so record & do next a
for(d=2; d<=sqrt(c); d++){
if(c%d==0){e=c/d; m2=1; break}} # If c has factors, the first factor found (d) is prime; if no factors,
if(m2==0){f2++;
continue}
# c is prime, a is 2-factor, so record & do next a
for(f=2; f<=sqrt(e); f++){
if(e%f==0){g=e/f; m3=1; break}} # If e has factors, the first factor found (f) is prime; if no factors,
if(m3==0){f3++;
continue}
# e is prime, a is 3-factor, so record and do next a
for(h=2; h<=sqrt(g); h++){
if(g%h==0){m4=1;
break}}
# If g has factors, the first factor found (h) is prime; if no factors,
if(m4==0){f4++;
continue}
# g is prime, a is 4-factor, so record and do next a
f5plus++}
# If g%h is positive, g has factors, therefore a has more than 4
# factors, so record and do next a
print "" >>o
print "Range "x" to "y >>o
print " Number of primes ",f1 >>o
print " Number of semiprimes ",f2 >>o
print " Number of 3-almost primes ",f3 >>o
print " Number of 4-almost primes ",f4 >>o
print " Number of all other numbers",f5plus+1 >>o
print " Total number check",f1+f2+f3+f4+f5plus+1 >>o
print "" >>o
f1=0; f2=0; f3=0; f4=0; f5plus=0
exit}