Gawk algorithm for finding numbers of k-almost primes    
(Dave Robinson, Brisbane, 2004: http://daverobinson.id.au)


                                                                            BACK TO ALMOST PRIMES



#  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}