From 8a3efb8fe4dd942185ada009d83a894dd7492042 Mon Sep 17 00:00:00 2001 From: Neil Smith Date: Fri, 17 Feb 2017 10:37:45 +0000 Subject: [PATCH 1/1] More tweakes to prime generation and testing --- euler35.ipynb | 198 +++++++++++++------------------------------------- euler35.rb | 30 ++++---- primes.rb | 14 +++- 3 files changed, 80 insertions(+), 162 deletions(-) diff --git a/euler35.ipynb b/euler35.ipynb index dcd6039..f3bda1b 100644 --- a/euler35.ipynb +++ b/euler35.ipynb @@ -2,7 +2,7 @@ "cells": [ { "cell_type": "code", - "execution_count": 1, + "execution_count": 25, "metadata": { "collapsed": false, "scrolled": true @@ -11,78 +11,23 @@ { "data": { "text/plain": [ - "#" + "#" ] }, - "execution_count": 1, + "execution_count": 25, "metadata": {}, "output_type": "execute_result" } ], "source": [ + "load 'array-numbers.rb'\n", "load 'primes.rb'\n", "$primes = Primes.instance" ] }, { "cell_type": "code", - "execution_count": 2, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "data": { - "text/plain": [ - ":to_r" - ] - }, - "execution_count": 2, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "class Array\n", - " def to_i\n", - " self.map {|d| d.to_s}.join.to_i\n", - " end\n", - " \n", - " def to_r\n", - " Rational(self[0].to_i, self[1].to_i)\n", - " end\n", - "end" - ] - }, - { - "cell_type": "code", - "execution_count": 3, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "data": { - "text/plain": [ - ":to_digits" - ] - }, - "execution_count": 3, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "class Integer\n", - " def to_digits\n", - " self.to_s.split('').map {|d| d.to_i}\n", - " end\n", - "end " - ] - }, - { - "cell_type": "code", - "execution_count": 4, + "execution_count": 26, "metadata": { "collapsed": false }, @@ -93,7 +38,7 @@ ":all_rotations" ] }, - "execution_count": 4, + "execution_count": 26, "metadata": {}, "output_type": "execute_result" } @@ -108,7 +53,7 @@ }, { "cell_type": "code", - "execution_count": 5, + "execution_count": 27, "metadata": { "collapsed": false }, @@ -119,7 +64,7 @@ "[[1, 2, 3], [2, 3, 1], [3, 1, 2]]" ] }, - "execution_count": 5, + "execution_count": 27, "metadata": {}, "output_type": "execute_result" } @@ -130,7 +75,7 @@ }, { "cell_type": "code", - "execution_count": 6, + "execution_count": 28, "metadata": { "collapsed": false }, @@ -141,7 +86,7 @@ "[123, 231, 312]" ] }, - "execution_count": 6, + "execution_count": 28, "metadata": {}, "output_type": "execute_result" } @@ -152,7 +97,7 @@ }, { "cell_type": "code", - "execution_count": 7, + "execution_count": 29, "metadata": { "collapsed": false }, @@ -163,7 +108,7 @@ "[false, false, false]" ] }, - "execution_count": 7, + "execution_count": 29, "metadata": {}, "output_type": "execute_result" } @@ -174,7 +119,7 @@ }, { "cell_type": "code", - "execution_count": 8, + "execution_count": 30, "metadata": { "collapsed": false }, @@ -185,7 +130,7 @@ "[true, true]" ] }, - "execution_count": 8, + "execution_count": 30, "metadata": {}, "output_type": "execute_result" } @@ -196,7 +141,7 @@ }, { "cell_type": "code", - "execution_count": 9, + "execution_count": 31, "metadata": { "collapsed": false }, @@ -207,7 +152,7 @@ "false" ] }, - "execution_count": 9, + "execution_count": 31, "metadata": {}, "output_type": "execute_result" } @@ -218,7 +163,7 @@ }, { "cell_type": "code", - "execution_count": 10, + "execution_count": 32, "metadata": { "collapsed": false }, @@ -229,7 +174,7 @@ "true" ] }, - "execution_count": 10, + "execution_count": 32, "metadata": {}, "output_type": "execute_result" } @@ -240,7 +185,7 @@ }, { "cell_type": "code", - "execution_count": 11, + "execution_count": 33, "metadata": { "collapsed": false }, @@ -251,19 +196,14 @@ ":circular_prime?" ] }, - "execution_count": 11, + "execution_count": 33, "metadata": {}, "output_type": "execute_result" } ], "source": [ "class Integer\n", - " @@primes = Primes.instance\n", - " \n", - " def prime?\n", - " @@primes.include? self\n", - " end\n", - " \n", + " \n", " def pl\n", " @@primes.primes.length\n", " end\n", @@ -276,43 +216,7 @@ }, { "cell_type": "code", - "execution_count": 11, - "metadata": { - "collapsed": false - }, - "outputs": [ - { - "data": { - "text/plain": [ - ":circular_prime?" - ] - }, - "execution_count": 11, - "metadata": {}, - "output_type": "execute_result" - } - ], - "source": [ - "class Integer\n", - " @@primes = Primes.instance\n", - " \n", - " def prime?\n", - " @@primes.include? self\n", - " end\n", - " \n", - " def pl\n", - " @@primes.primes.length\n", - " end\n", - " \n", - " def circular_prime?\n", - " self.to_digits.all_rotations.map {|n| n.to_i}.all? {|n| n.prime?} if self.prime?\n", - " end\n", - "end" - ] - }, - { - "cell_type": "code", - "execution_count": 12, + "execution_count": 34, "metadata": { "collapsed": false }, @@ -323,7 +227,7 @@ "1229" ] }, - "execution_count": 12, + "execution_count": 34, "metadata": {}, "output_type": "execute_result" } @@ -334,7 +238,7 @@ }, { "cell_type": "code", - "execution_count": 13, + "execution_count": 35, "metadata": { "collapsed": false }, @@ -345,7 +249,7 @@ "[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97]" ] }, - "execution_count": 13, + "execution_count": 35, "metadata": {}, "output_type": "execute_result" } @@ -356,7 +260,7 @@ }, { "cell_type": "code", - "execution_count": 14, + "execution_count": 36, "metadata": { "collapsed": false }, @@ -367,7 +271,7 @@ "[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97]" ] }, - "execution_count": 14, + "execution_count": 36, "metadata": {}, "output_type": "execute_result" } @@ -378,7 +282,7 @@ }, { "cell_type": "code", - "execution_count": 15, + "execution_count": 37, "metadata": { "collapsed": false }, @@ -389,7 +293,7 @@ "13" ] }, - "execution_count": 15, + "execution_count": 37, "metadata": {}, "output_type": "execute_result" } @@ -400,7 +304,7 @@ }, { "cell_type": "code", - "execution_count": 16, + "execution_count": 38, "metadata": { "collapsed": false }, @@ -412,7 +316,7 @@ }, { "cell_type": "code", - "execution_count": 17, + "execution_count": 39, "metadata": { "collapsed": false }, @@ -423,7 +327,7 @@ }, { "cell_type": "code", - "execution_count": 18, + "execution_count": 40, "metadata": { "collapsed": false }, @@ -432,7 +336,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "Time elapsed 0.125950399 seconds, going from 1229 to 1230 primes cached\n" + "Time elapsed 0.054970036 seconds, going from 1229 to 1230 primes cached\n" ] }, { @@ -441,7 +345,7 @@ "33" ] }, - "execution_count": 18, + "execution_count": 40, "metadata": {}, "output_type": "execute_result" } @@ -458,7 +362,7 @@ }, { "cell_type": "code", - "execution_count": 19, + "execution_count": 41, "metadata": { "collapsed": false }, @@ -467,7 +371,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "Time elapsed 0.123380027 seconds, going from 1230 to 1230 primes cached\n" + "Time elapsed 0.067191288 seconds, going from 1230 to 1230 primes cached\n" ] }, { @@ -476,7 +380,7 @@ "33" ] }, - "execution_count": 19, + "execution_count": 41, "metadata": {}, "output_type": "execute_result" } @@ -493,7 +397,7 @@ }, { "cell_type": "code", - "execution_count": 20, + "execution_count": 42, "metadata": { "collapsed": false }, @@ -502,7 +406,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "Time elapsed 9.59874264 seconds, going from 1230 to 9593 primes cached\n" + "Time elapsed 0.448493896 seconds, going from 1230 to 9593 primes cached\n" ] }, { @@ -511,7 +415,7 @@ "43" ] }, - "execution_count": 20, + "execution_count": 42, "metadata": {}, "output_type": "execute_result" } @@ -528,7 +432,7 @@ }, { "cell_type": "code", - "execution_count": 21, + "execution_count": 43, "metadata": { "collapsed": false }, @@ -537,7 +441,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "Time elapsed 7.768858416 seconds, going from 9593 to 9593 primes cached\n" + "Time elapsed 0.274737814 seconds, going from 9593 to 9593 primes cached\n" ] }, { @@ -546,7 +450,7 @@ "43" ] }, - "execution_count": 21, + "execution_count": 43, "metadata": {}, "output_type": "execute_result" } @@ -563,7 +467,7 @@ }, { "cell_type": "code", - "execution_count": 22, + "execution_count": 44, "metadata": { "collapsed": false }, @@ -572,7 +476,7 @@ "name": "stdout", "output_type": "stream", "text": [ - "Time elapsed 710.264030183 seconds, going from 9593 to 78499 primes cached\n" + "Time elapsed 10.457163873 seconds, going from 9593 to 78499 primes cached\n" ] }, { @@ -581,7 +485,7 @@ "55" ] }, - "execution_count": 22, + "execution_count": 44, "metadata": {}, "output_type": "execute_result" } @@ -598,7 +502,7 @@ }, { "cell_type": "code", - "execution_count": 23, + "execution_count": 47, "metadata": { "collapsed": false }, @@ -607,16 +511,16 @@ "name": "stdout", "output_type": "stream", "text": [ - "Time elapsed 597.009405584 seconds, going from 78499 to 78499 primes cached\n" + "Time elapsed 2.884361875 seconds, going from 78499 to 78499 primes cached\n" ] }, { "data": { "text/plain": [ - "55" + "[2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97, 113, 131, 197, 199, 311, 337, 373, 719, 733, 919, 971, 991, 1193, 1931, 3119, 3779, 7793, 7937, 9311, 9377, 11939, 19391, 19937, 37199, 39119, 71993, 91193, 93719, 93911, 99371, 193939, 199933, 319993, 331999, 391939, 393919, 919393, 933199, 939193, 939391, 993319, 999331]" ] }, - "execution_count": 23, + "execution_count": 47, "metadata": {}, "output_type": "execute_result" } @@ -628,7 +532,7 @@ "end_time = Time.now\n", "pl1 = 0.pl\n", "puts \"Time elapsed #{(end_time - beginning_time)} seconds, going from #{pl0} to #{pl1} primes cached\"\n", - "cps.length" + "cps" ] }, { diff --git a/euler35.rb b/euler35.rb index d2ba75d..a25edfe 100644 --- a/euler35.rb +++ b/euler35.rb @@ -1,14 +1,15 @@ require 'ruby-prof' load 'primes.rb' +load 'array-numbers.rb' class Array - def to_i - self.map {|d| d.to_s}.join.to_i - end +# def to_i +# self.map {|d| d.to_s}.join.to_i +# end - def to_r - Rational(self[0].to_i, self[1].to_i) - end +# def to_r +# Rational(self[0].to_i, self[1].to_i) +# end def all_rotations (0...self.length).map {|r| self.rotate(r)} @@ -16,26 +17,27 @@ class Array end class Integer - @@primes = Primes.instance +# @@primes = Primes.instance - def prime? - @@primes.include? self - end +# def prime? +# @@primes.include? self +# end def pl @@primes.primes.length end def circular_prime? - self.to_digits.all_rotations.map {|n| n.to_i}.all? {|n| n.prime?} if self.prime? + self.prime? && self.to_digits.all_rotations.map {|n| n.to_i}.all? {|n| n.prime?} end - def to_digits - self.to_s.split('').map {|d| d.to_i} - end + # def to_digits + # self.to_s.split('').map {|d| d.to_i} + # end end + RubyProf.start # (10**6).prime? diff --git a/primes.rb b/primes.rb index 7e2cfaa..b254fab 100644 --- a/primes.rb +++ b/primes.rb @@ -95,10 +95,21 @@ class Primes while n >= @primes.last add_next_prime! end - # @primes.include?(n) !!(@primes.bsearch {|i| n - i}) end + # Use this if you're only testing a few primes and not needing to generate many more. + def is_prime?(n) + return true if n == 2 + return false if n < 2 + limit = Math.sqrt(n).floor + while @primes.last <= limit + add_next_prime! + end + index = @primes.bsearch_index {|i| i > limit} || @primes.length + @primes[0..index].none? {|i| n % i == 0} + end + end @@ -107,5 +118,6 @@ class Integer def prime? @@primes.include? self + # @@primes.is_prime? self end end -- 2.34.1