--00163630f08bd0aab9049f3529b8 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Nice I dint know about the Prime class available in stdlib. Thanks a lot.. :) --Mayank On Thu, Mar 24, 2011 at 8:34 AM, serialhex <serialhex / gmail.com> wrote: > hey all, > so while Jesus's implementation works, unless you want to implement a > prime number generator yourself you're probably better off using Rubys > built-in Prime class (doc here: http://rdoc.info/stdlib/prime/1.9.2/frames) > to do this. not only does it give you cleaner code, it is SIGNIFICANTLY > faster. > > # the spiffified code > require 'prime' # you're gonna need this > require 'mathn' # you're gonna want this > > class PrimeFactor > def initialize(number) > @number = number > end > > def primeFactors > @factors = Prime.prime_division(@number, > Prime::TrialDivisionGenerator.new).flatten.uniq.sort.join(', ') > end > > end > > #prime = PrimeFactor.new(13195) > prime = PrimeFactor.new(ARGV.shift.to_i) > puts "#{prime.primeFactors}" > > in fact, benchmarking the two thusly: > > # the benchmark code: > require 'prime' # you're gonna need this > require 'mathn' # you're gonna want this > > require 'benchmark' > > class PrimeFactor_Long > def initialize(number) > @number = number > end > > def primeFactors > factors = Array.new > (2..@number).each do |num| > if ( @number % num == 0 ) > factors.insert(factors.length,num) > end > end > # p factors > factors.each do |factor| > next if factor.nil? > factors.each_with_index do |candidate,i| > next if candidate == factor > next if candidate.nil? > factors[i] = nil if candidate % factor == 0 > end > end > factors.compact.join(',') > end > end > > class PrimeFactor_Shrt > def initialize(number) > @number = number > end > > def primeFactors > factors = Prime.prime_division(@number, > Prime::TrialDivisionGenerator.new).flatten.uniq.sort.join(', ') > end > > end > > lots = 13195 > > bunches_of = 1_000 > > Benchmark.bmbm do |x| > x.report('Long') do > bunches_of.times do > long = PrimeFactor_Long.new lots > long.primeFactors > end > end > x.report('Shrt') do > bunches_of.times do > shrt = PrimeFactor_Shrt.new lots > shrt.primeFactors > end > end > end > > puts > > long = PrimeFactor_Long.new lots > puts "long factors: #{long.primeFactors}" > > shrt = PrimeFactor_Shrt.new lots > puts "shrt factors: #{long.primeFactors}" > > > gives this: > serialhex@livecd:~/src/test> ruby bench_prime.rb > Rehearsal ---------------------------------------- > Long 3.160000 0.070000 3.230000 ( 3.523138) > Shrt 0.050000 0.000000 0.050000 ( 0.070737) > ------------------------------- total: 3.280000sec > > user system total real > Long 3.010000 0.030000 3.040000 ( 3.227173) > Shrt 0.060000 0.000000 0.060000 ( 0.070470) > > long factors: 5,7,13,29 > shrt factors: 5,7,13,29 > > no joke... it's more than 50x faster :P so yeah, unless this is a project > for a class or something, use the included Prime class! > hex > > > > > 2011/3/23 Jesù¸ Gabriel y GaláÏ <jgabrielygalan / gmail.com> > > > On Wed, Mar 23, 2011 at 10:57 AM, Mayank K. <mayank.kohaley / gmail.com> > > wrote: > > > I am trying to execute the following code and it seems like the array > is > > > going out of bounds. Let me know where am I going wrong. > > > > > > class PrimeFactor > > > def initialize(number) > > > @number = number > > > end > > > > > > def primeFactors > > > factors = Array.new > > > (2..Math.sqrt(@number).ceil).each do |num| > > > if ( @number % num == 0 ) > > > factors.insert(factors.length,num) > > > end > > > end > > > (0...factors.length).each do |i| > > > prime = factors[i] > > > factors = factors.select { |x| x == prime || x % prime !=0 } > > > end > > > > > > factors.compact.join(',') > > > end > > > end > > > > > > prime = PrimeFactor.new(13195) > > > puts "#{prime.primeFactors}" > > > > > > C:\Temp\Study\Ruby>ruby --version > > > ruby 1.8.7 (2011-02-18 patchlevel 334) [i386-mingw32] > > > > > > C:\Temp\Study\Ruby>ruby prime.rb > > > prime.rb:16:in `%': nil can't be coerced into Fixnum (TypeError) > > > from prime.rb:16:in `primeFactors' > > > from prime.rb:16:in `select' > > > from prime.rb:16:in `primeFactors' > > > from prime.rb:14:in `each' > > > from prime.rb:14:in `primeFactors' > > > from prime.rb:24 > > > > The problem with your code is that you are modifying the factors array > > inside a precalculated iteration. Try adding some print statements in > > the last loop you'll see what's going on: > > > > [... snip...] > > p factors.length > > (0...factors.length).each do |i| > > p factors > > p i > > prime = factors[i] > > factors = factors.select { |x| x == prime || x % prime !=0 } > > end > > > > As you'll see, you are modifying the array, but the each loop is still > > going from 0 to 7. Another approach could be to set to nil the > > multiples of each factor, and then compact: > > > > factors.each do |factor| > > next if factor.nil? > > factors.each_with_index do |candidate,i| > > next if candidate == factor > > factors[i] = nil if candidate % factor == 0 > > end > > end > > > > BTW, your logic about the Math.sqrt being the top possible factor is > > wrong (that's used to know if a number is prime). For example, for 15, > > Math.sqrt(15) is less than 4, and 5 is a factor of 15 which your logic > > will skip. All in all, this works: > > > > class PrimeFactor > > def initialize(number) > > @number = number > > end > > > > def primeFactors > > factors = Array.new > > (2..@number).each do |num| > > if ( @number % num == 0 ) > > factors.insert(factors.length,num) > > end > > end > > p factors > > factors.each do |factor| > > next if factor.nil? > > factors.each_with_index do |candidate,i| > > next if candidate == factor > > next if candidate.nil? > > factors[i] = nil if candidate % factor3D= > 0 > > end > > end > > factors.compact.join(',') > > end > > end > > > > #prime = PrimeFactor.new(13195) > > prime = PrimeFactor.new(ARGV.shift.to_i) > > puts "#{prime.primeFactors}" > > > > Maybe it can be further optimized, but you can start from here. This > > is the ouput for 13195: > > > > $ ruby prime_factors.rb 13195 > > [5, 7, 13, 29, 35, 65, 91, 145, 203, 377, 455, 1015, 1885, 2639, 13195] > > 5,7,13,29 > > > > Jesus. > > > > > -- Mayank Kohaley --00163630f08bd0aab9049f3529b8--