Prime factorization using Ruby

# defines a number N whose prime factors will be found N = 5605927 isitprime = 0 # generates array of primes up to the square root of N primes = [2,3] (4..Math.sqrt(N).floor).each do |i| (0..primes.length-1).each do |j| if i % primes[j] == 0 isitprime = 0 break else isitprime = 1 end end if isitprime == 1 primes << i end end # tests divisibility into N and divides out factors n = N factors = [] while n > 1 # tests for prime factors smaller than the square root of N (0..primes.length-1).each do |k| if n % primes[k] == 0 n = n/primes[k] factors << primes[k] redo end end # tests for special case: N is prime if n == N n = 1 end # tests for special case: N has one prime factor that is greater than the square root of N if n > Math.sqrt(N).floor factors << n n = 1 end end # outputs prime factors if factors.length > 0 puts "the prime factors of #{N} are" puts factors.sort else puts "#{N} is prime" end
Finds the prime factors of some number N using Ruby

#prime #numbers #factorization #factors



Be the first to comment

You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.