Calculating the prime factors of a very large number

question:
How would you write the code to find the prime factors of a very large
number?

I think one of the factors is small (ie) less than 1000
the code I have written is:

print ’ please enter num: ’
num_one=gets.chomp.to_i
data = []
for x in (3…1000)
if x%2!=0 then
a = (x+1)/2
for i in (2…a)
if (x%i!=0)then
if i==a then
if num_one% x==x then
num_one/x=y
data <<x
print x
print y
end
end
end

end

end
end

#the large numbers given num_one and num_two are both odd

num_one =
21072236091611056689769183170665611839100660350189688162526899493835280729017620910006683962065747474746709582322870618924665901484145427690586656845288518421681715673619112289711701720430391346045498245691129378838117217972370441489717683798051804677941408786220581644893272649652708260725883926679251761833970410399147125916239687836131680486047711823435095777510281209932021075855270719904838238244264978537530033246226019262901302259332326201118956583817393649845723329843569413127263570255051462833626736607380988962342059574997647316022718247287419422282235170644994619557795227339530396253222625063056535813277

num_2 =
180980229898927614895852399429117101465275605765423295969005441424411086519047965226517527209287034243869824254236654269650778738505603896097810603554472797099957268999735645451862866599047554310106053073400016747052276933651693201994493045313861124048732077888820269415257040728350248748917830864512468597941793613527384250273032074597581295632021919688417670849218802439787068450273090792416213728427471241952690295098911214297345232764670796463979696711452531294829870748197355206752754348990795971540090615346527922888200122030125438669554525381727289927496029752456560988927002888169535698458197751522390933149786001

##I need help in writing the code, am I on the right track?

On Fri, Nov 11, 2011 at 11:46 PM, Ja xv [email protected]
wrote:

question:
How would you write the code to find the prime factors of a very large
number?

I think one of the factors is small (ie) less than 1000
the code I have written is:

##I need help in writing the code, am I on the right track?

I am not sure what you are looking for: are you looking for feedback
on your specific code or are you looking for efficient prime
factorization algorithms? In the latter, there are quire a few around
and documented, for example at

http://en.wikipedia.org/wiki/Category:Integer_factorization_algorithms

For example this one: http://en.wikipedia.org/wiki/Quadratic_sieve

Kind regards

robert

hello

require “prime”

primes = []
Prime.each {|n| primes << n ; break if n > 4000 }
p primes.last

factors = Prime.prime_division(12_000)
p factors

prints

4001
[[2, 5], [3, 1], [5, 3]]

hope this helps

Ja xv wrote in post #1031499:

question:
How would you write the code to find the prime factors of a very large
number?

I think one of the factors is small (ie) less than 1000
the code I have written is:

print ’ please enter num: ’
num_one=gets.chomp.to_i
data = []
for x in (3…1000)
if x%2!=0 then
a = (x+1)/2
for i in (2…a)
if (x%i!=0)then
if i==a then
if num_one% x==x then
num_one/x=y
data <<x
print x
print y
end
end
end

end

end
end

#the large numbers given num_one and num_two are both odd

num_one =

21072236091611056689769183170665611839100660350189688162526899493835280729017620910006683962065747474746709582322870618924665901484145427690586656845288518421681715673619112289711701720430391346045498245691129378838117217972370441489717683798051804677941408786220581644893272649652708260725883926679251761833970410399147125916239687836131680486047711823435095777510281209932021075855270719904838238244264978537530033246226019262901302259332326201118956583817393649845723329843569413127263570255051462833626736607380988962342059574997647316022718247287419422282235170644994619557795227339530396253222625063056535813277

num_2 =

180980229898927614895852399429117101465275605765423295969005441424411086519047965226517527209287034243869824254236654269650778738505603896097810603554472797099957268999735645451862866599047554310106053073400016747052276933651693201994493045313861124048732077888820269415257040728350248748917830864512468597941793613527384250273032074597581295632021919688417670849218802439787068450273090792416213728427471241952690295098911214297345232764670796463979696711452531294829870748197355206752754348990795971540090615346527922888200122030125438669554525381727289927496029752456560988927002888169535698458197751522390933149786001

##I need help in writing the code, am I on the right track?

On 11/14/2011 05:57 AM, Marc H. wrote:

require “prime”

^^^ Is this specific to Ruby 1.9.x ?

There’s a Prime class that’s available if you require ‘mathn’

On 11/14/2011 05:57 AM, Marc H. wrote:

require “prime”

^^^ Is this specific to Ruby 1.9.x ?

Guess I should have looked at the other message closer. There’s a Prime
class in mathn but it’s not the same as the one from Ruby 1.9.

Marc H. wrote in post #1031759:

require “prime”

^^^ Is this specific to Ruby 1.9.x ?

Yes it is specific to 1.9

maybe you can be interested in Miller-Rabin prime test in Ruby (search
on web)

require “prime”

^^^ Is this specific to Ruby 1.9.x ?

-----Messaggio originale-----
Da: Giampiero Z. [mailto:[email protected]]
Inviato: luned 14 novembre 2011 15:10
A: ruby-talk ML
Oggetto: Re: calculating the prime factors of a very large number

Marc H. wrote in post #1031759:

require “prime”

^^^ Is this specific to Ruby 1.9.x ?

Yes it is specific to 1.9

maybe you can be interested in Miller-Rabin prime test in Ruby (search
on
web)


Posted via http://www.ruby-forum.com/.


Caselle da 1GB, trasmetti allegati fino a 3GB e in piu’ IMAP, POP3 e
SMTP autenticato? GRATIS solo con Email.it http://www.email.it/f

Sponsor:
Conto Arancio al 4,20%. Zero spese e massima liberta’, aprilo in due
minuti!
Clicca qui: http://adv.email.it/cgi-bin/foclick.cgi?mid919&d)-12

-----Messaggio originale-----
Da: Ja xv [mailto:[email protected]]
Inviato: venerd 11 novembre 2011 23:47
A: ruby-talk ML
Oggetto: calculating the prime factors of a very large number

question:
How would you write the code to find the prime factors of a very large
number?

I think one of the factors is small (ie) less than 1000 the code I have
written is:

print ’ please enter num: ’
num_one=gets.chomp.to_i
data = []
for x in (3…1000)
if x%2!=0 then
a = (x+1)/2
for i in (2…a)
if (x%i!=0)then
if i==a then
if num_one% x==x then
num_one/x=y
data <<x
print x
print y
end
end
end

end

end
end

#the large numbers given num_one and num_two are both odd

num_one =
2107223609161105668976918317066561183910066035018968816252689949383528072901
7620910006683962065747474746709582322870618924665901484145427690586656845288
5184216817156736191122897117017204303913460454982456911293788381172179723704
4148971768379805180467794140878622058164489327264965270826072588392667925176
1833970410399147125916239687836131680486047711823435095777510281209932021075
8552707199048382382442649785375300332462260192629013022593323262011189565838
1739364984572332984356941312726357025505146283362673660738098896234205957499
7647316022718247287419422282235170644994619557795227339530396253222625063056
535813277

num_2 =
1809802298989276148958523994291171014652756057654232959690054414244110865190
4796522651752720928703424386982425423665426965077873850560389609781060355447
2797099957268999735645451862866599047554310106053073400016747052276933651693
2019944930453138611240487320778888202694152570407283502487489178308645124685
9794179361352738425027303207459758129563202191968841767084921880243978706845
0273090792416213728427471241952690295098911214297345232764670796463979696711
4525312948298707481973552067527543489907959715400906153465279228882001220301
2543866955452538172728992749602975245656098892700288816953569845819775152239
0933149786001

##I need help in writing the code, am I on the right track?


Posted via http://www.ruby-forum.com/.


Caselle da 1GB, trasmetti allegati fino a 3GB e in piu’ IMAP, POP3 e
SMTP autenticato? GRATIS solo con Email.it http://www.email.it/f

Sponsor:
Conto Arancio al 4,20%. Soldi sempre disponibili, zero spese, aprilo in
due minuti!
Clicca qui: http://adv.email.it/cgi-bin/foclick.cgi?mid920&d)-12

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs