I developed Awk code to print all primes till N where N is given as command line argument. I think I took pretty much all the optimizations into account. Could someone help if it could be optimized even more. The code is as follows:
#!/usr/bin/awk -f
BEGIN{
for (i=oddify(ARGV[1]); i>2; i=i-2){
flag=1 #prime
for(j=3; j<=ceil(sqrt(i)); j=j+2){
if (i%j==0){
flag=0 #not prime
break
}
}
if (flag==1){printf("%d\n", i) }
}
printf("2\n")
}
function ceil(n){
return (n == int(n)) ? n : int(n)+1
}
function oddify(n){
return (n%2 != 0) ? n : n-1
}
How to run: awk -f prime.awk 10000
1 Answer 1
Bug: when I run the program with argument 1, it prints 2 even though 2> 1.
The code is not optimized at all. It computes ceil and sqrt way too often, in a way that is obvious to optimize. All other prime programs on this site already do that, have a look at them.
The code is not optimized enough. It contains i = i + 2, which should have been i += 2 from the beginning. A third of these calls can be omitted using the standard prime searching technique that has been mentioned more than enough on this site.
The variable name flag is terrible. It should be is_prime instead.
Having the most interesting code in the BEGIN block is bad design. You should define a function is_prime and another function print_primes_up_to. This allows you to declare i and j as local variables.
In the function ceil, the parameter name n is confusing since this name implies to the human reader that it is a natural number. In reality it is a floating point number though. A better name for this variable is x.
The code is missing some documentation. It should clearly state up to which number it reports correct results. It should also state the first number for which a wrong result is printed. Internally, many AWK implementations use 64-bit floating point numbers, therefore I guess this number is somewhere around \2ドル^{53}\$.