Miller–Rabin primality test: Difference between revisions

Content added Content deleted
Line 1,090: Line 1,090:


struct Int; include Primes::MillerRabin end
struct Int; include Primes::MillerRabin end

def tm; t = Time.now; yield; Time.now - t end


# 10 digit prime
# 10 digit prime
n = 2147483647
n = 2147483647
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


# 18 digit non-prime
# 18 digit non-prime
n = 844674407370955389
n = 844674407370955389
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


# 19 digit prime
# 19 digit prime
n = 9241386435364257883.to_big_i
n = 9241386435364257883.to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


# 20 digit prime; largest < 2^64
# 20 digit prime; largest < 2^64
n = 18446744073709551533.to_big_i
n = 18446744073709551533.to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


# 58 digit prime
# 58 digit prime
n = "4547337172376300111955330758342147474062293202868155909489".to_big_i
n = "4547337172376300111955330758342147474062293202868155909489".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


# 58 digit non-prime
# 58 digit non-prime
n = "4547337172376300111955330758342147474062293202868155909393".to_big_i
n = "4547337172376300111955330758342147474062293202868155909393".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


# 81 digit prime
# 81 digit prime
n = "100000000000000000000000000000000000000000000000000000000000000000000000001309503".to_big_i
n = "100000000000000000000000000000000000000000000000000000000000000000000000001309503".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


# 81 digit non-prime
# 81 digit non-prime
n = "100000000000000000000000000000000000000000000000000000000000000000000000001309509".to_big_i
n = "100000000000000000000000000000000000000000000000000000000000000000000000001309509".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


# 308 digit prime
# 308 digit prime
n = "94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881".to_big_i
n = "94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


n = "138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401".to_big_i
n = "138028649176899647846076023812164793645371887571371559091892986639999096471811910222267538577825033963552683101137782650479906670021895135954212738694784814783986671046107023185842481502719762055887490765764329237651328922972514308635045190654896041748716218441926626988737664133219271115413563418353821396401".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


n = "123301261697053560451930527879636974557474268923771832437126939266601921428796348203611050423256894847735769138870460373141723679005090549101566289920247264982095246187318303659027201708559916949810035265951104246512008259674244307851578647894027803356820480862664695522389066327012330793517771435385653616841".to_big_i
n = "123301261697053560451930527879636974557474268923771832437126939266601921428796348203611050423256894847735769138870460373141723679005090549101566289920247264982095246187318303659027201708559916949810035265951104246512008259674244307851578647894027803356820480862664695522389066327012330793517771435385653616841".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


n = "119432521682023078841121052226157857003721669633106050345198988740042219728400958282159638484144822421840470442893056822510584029066504295892189315912923804894933736660559950053226576719285711831138657839435060908151231090715952576998400120335346005544083959311246562842277496260598128781581003807229557518839".to_big_i
n = "119432521682023078841121052226157857003721669633106050345198988740042219728400958282159638484144822421840470442893056822510584029066504295892189315912923804894933736660559950053226576719285711831138657839435060908151231090715952576998400120335346005544083959311246562842277496260598128781581003807229557518839".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


n = "132082885240291678440073580124226578272473600569147812319294626601995619845059779715619475871419551319029519794232989255381829366374647864619189704922722431776563860747714706040922215308646535910589305924065089149684429555813953571007126408164577035854428632242206880193165045777949624510896312005014225526731".to_big_i
n = "132082885240291678440073580124226578272473600569147812319294626601995619845059779715619475871419551319029519794232989255381829366374647864619189704922722431776563860747714706040922215308646535910589305924065089149684429555813953571007126408164577035854428632242206880193165045777949624510896312005014225526731".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


n = "153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599".to_big_i
n = "153410708946188157980279532372610756837706984448408515364579602515073276538040155990230789600191915021209039203172105094957316552912585741177975853552299222501069267567888742458519569317286299134843250075228359900070009684517875782331709619287588451883575354340318132216817231993558066067063143257425853927599".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


n = "103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041".to_big_i
n = "103130593592068072608023213244858971741946977638988649427937324034014356815504971087381663169829571046157738503075005527471064224791270584831779395959349442093395294980019731027051356344056416276026592333932610954020105156667883269888206386119513058400355612571198438511950152690467372712488391425876725831041".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts


n = "94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881".to_big_i
n = "94366396730334173383107353049414959521528815310548187030165936229578960209523421808912459795329035203510284576187160076386643700441216547732914250578934261891510827140267043592007225160798348913639472564715055445201512461359359488795427875530231001298552452230535485049737222714000227878890892901228389026881".to_big_i
puts "\n number = #{n} is prime? is #{n.primemr?}"
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts

</lang>
</lang>


Retrieved from "https://rosettacode.org/wiki/Miller–Rabin_primality_test"