Revision: 61639
Updated Code
at December 31, 2012 02:57 by the_blizz
Updated Code
# 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
Revision: 61638
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at December 31, 2012 02:55 by the_blizz
Initial Code
# this script finds the prime factors of a number N, reasonably quickly for numbers up to 10 digits or so
# 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
Initial URL
Initial Description
finds the prime factors of some number N
Initial Title
prime factorization
Initial Tags
Initial Language
Ruby