How quick will it be?
OMP operative seems to slow down the operations. Maybe inappropriate place for it.
Compile using gfortran:
gfortran -O3 -march=native -mtune=native -funroll-loops -floop-block -fopenmp --free-form utilities.f90 prime_finder.f90
Run with:
time ./a.out