Advanced Search

prime factorization

/ Published in: Ruby
Save to your folder(s)
finds the prime factors of some number N

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. # defines a number N whose prime factors will be found
  2.  
  3. N = 5605927
  4. isitprime = 0
  5.  
  6. # generates array of primes up to the square root of N
  7.  
  8. primes = [2,3]
  9.  
  10. (4..Math.sqrt(N).floor).each do |i|
  11. 	(0..primes.length-1).each do |j|
  12. 		if i % primes[j] == 0
  13. 			isitprime = 0
  14. 			break
  15. 		else 
  16. 			isitprime = 1
  17. 		end		
  18. 		end
  19. 	if isitprime == 1
  20. 		primes << i
  21. 	end
  22. end
  23.  
  24. # tests divisibility into N and divides out factors
  25.  
  26. n = N
  27. factors = []
  28.  
  29. while n > 1
  30.  
  31. 	# tests for prime factors smaller than the square root of N
  32.  
  33. 	(0..primes.length-1).each do |k|
  34. 		if n % primes[k] == 0
  35. 			n = n/primes[k]
  36. 			factors << primes[k]	
  37. 			redo		
  38. 		end
  39. 	end
  40.  
  41. 	# tests for special case: N is prime
  42.  
  43. 	if n == N
  44. 		n = 1	
  45. 	end
  46.  
  47. 	# tests for special case: N has one prime factor that is greater than the square root of N
  48.  
  49. 	if n > Math.sqrt(N).floor
  50. 		factors << n
  51. 		n = 1
  52. 	end
  53.  
  54. end
  55.  
  56. # outputs prime factors
  57.  
  58. if factors.length > 0
  59. 	puts "the prime factors of #{N} are"
  60. 	puts factors.sort
  61. else
  62. 	puts "#{N} is prime"
  63. end

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.