Posted By

the_blizz on 12/31/12


Tagged


Versions (?)

prime factorization


 / Published in: Ruby
 

finds the prime factors of some number N

  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  

You need to login to post a comment.