Algorithem Matters to Performance

If we want to find all Prime number within a positive range, how would you figure it out? I want to share with you with a simple code on how algorithm matters to performance: I am using Ruby to demo the difference between 2 ways to organize your code and how they impact the performance: Without any optimization:

 require 'ruby-prof'  
 def findprimenumber(uppernumber)   
  count =0;   
  for i in 3..uppernumber   
   primebool = true;   
   for j in 2...i   
    if (i%j!=0)   
    next;   
    else   
    primebool = false;   
    break;   
    end   
   end   
   if(primebool)   
   count= count+1   
   end   
  end   
  puts("total prime count:#{count}");   
  puts RubyProf.measure_process_time   
  end   

With optimization:

 require 'ruby-prof'   
 def findprimenumberopt(uppernumber)   
  count =0;   
  for i in 3..uppernumber   
   primebool = true;   
   if i%2==0   
   primebool = false;   
   next;   
   else   
   *for j in 3..Math.sqrt(i).floor+1 *  
    if (i%j!=0)   
    next;   
    else   
    primebool = false;   
    break;   
    end   
    *j=j+2;*  
   end   
   end   
   if(primebool)   
   count= count+1   
   end   
  end   
  puts("total prime count:#{count}");   
  puts RubyProf.measure_process_time   
  end   

Given the uppernumber to 100000 The performance result without optimization code :47s The performance result with optimization code :0.9s Also you may try more optimization way such as divide and conquer by parallel computing...