PE

何度も実行される箇所で Linq を使うことによるパフォーマンスの影響

Project Euler 23 を解いていて、Linq 使用の有無で速度差が出たのでメモ。 約数の和を求める SumProperDivisors メソッドで Linq を使う場合と、Linq を使わずに for 文で計算する場合とでどれくらい速度に差が出るか計測してみました。 using System; usin…

Project Euler 56

PE

Problem 56 using System; using System.Collections.Generic; using System.Numerics; using System.Linq; class PE056 { static void Main() { var seq = from a in Enumerable.Range(1, 99) from b in Enumerable.Range(1, 99) let sum = BigInteger.Pow(…

Project Euler 55

PE

Problem 55 using System; using System.Collections.Generic; using System.Numerics; using System.Linq; // コンパイル方法: // $ mcs 055.cs -r:System.Numerics -out:a.exe class PE055 { static bool IsPalindrome(BigInteger n) { var a = n.ToString…

Project Euler 52

PE

Problem 52 6 倍しても桁が変わらないので、最上位の桁は 1 のはず。 using System; using System.Collections.Generic; using System.Linq; class PE052 { static void Main() { for (int i = 1; /* */; i++) { string s = "1" + i; // 6 倍しても桁数が同…

Project Euler 50

PE

Problem 50 using System; using System.Collections.Generic; using System.Linq; class Prime { public static List<int> Sieve(int n) { // n 以下の全ての素数を求める bool[] tab = new bool[n+1]; for (int i = 0; i < tab.Length; i++) tab[i] = true; int</int>…

Project Euler 49

PE

Problem 49 using System; using System.Collections.Generic; using System.Linq; class Prime { public static List<int> Sieve(int n) { // n 以下の全ての素数を求める bool[] tab = new bool[n+1]; for (int i = 0; i < tab.Length; i++) tab[i] = true; int</int>…

Project Euler 46

C# PE

Problem 46 using System; class PE046 { static bool IsPrime(int n) { if (n == 2) return true; if (n % 2 == 0) return false; for (int i = 3; i*i <= n; i += 2) { if (n % i == 0) { return false; } } return true; } // n == prime * 2*x*x という…

Project Euler 43

C# PE

Problem 43 using System; using System.Collections.Generic; using System.Linq; class PE043 { static long Calc(int p, int[] digits, bool[] used) { int[] ds = { 0, 0, 2, 3, 5, 7, 11, 13, 17 }; long ret = 0; int x = 100 * digits[p-3] + 10 * di…

Project Euler 42

Problem 42 using System; using System.Collections.Generic; using System.IO; using System.Text.RegularExpressions; using System.Linq; class PE042 { static bool IsTriangleWord(string word) { int sum = word.Select(c => c - 'A' + 1).Sum(); int…

Project Euler 41

C# PE

Problem 41 リストの要素を swap する関数は stackoverflow の以下を参考にしました。 c# - Swap two items in List<T> - Stack Overflow using System; using System.Collections.Generic; using System.Linq; class PE041 { static void Swap<T>(List<T> ls, int a,</t></t></t>…

Project Euler 40

PE C#

Problem 40 10 から 99 までの整数をつなげたとき、その桁数は 桁数:2 * (100 - 10) です。 100 から 999 までの整数をつながたとき、その桁数は 桁数:3 * (1000 - 100) です。 $ pry [3] pry(main)> x = 10 => 10 [4] pry(main)> x.to_s.length * (10*x - x…

Project Euler 39

C# PE

Problem 39 right angle triangle とは直角三角形のこと p <= 1000 なので、1 辺の長さは 500 まで調べる using System; using System.Collections.Generic; using System.Linq; class PE039 { static void Main() { const int N = 500; var freq = new Dict…

Project Euler 38

C# PE

Problem 38 n > 1 なので 100000 まで調べている。もっと値は小さくできそうだけど……。 using System; class PE038 { static int Calc(int n) { string s = ""; for (int i = 1; ; i++) { s += (n * i).ToString(); int[] freq = new int[10]; int m = 0; fo…

Project Euler 37

C# PE

Problem 37 using System; using System.Collections.Generic; using System.Linq; class PE037 { static List<int> MakePrimes(int n) { var primes = new List<int>(); primes.Add(2); // 2 is prime var table = new bool[n+1]; for (int i = 3; i <= n; i += 2) { </int></int>…

Project Euler 36

C# PE

Problem 36 2 進数の回文は、末尾が必ず 1 となるので、奇数のみ調べる。 using System; using System.Collections.Generic; using System.Linq; class PE036 { static string Bin(int n) { if (n < 0) throw new Exception("n < 0"); var ls = new List<char>(); </char>…

Project Euler 35

PE C#

Problem 35 1000000 までの素数を求める(エラトステネスのふるいで素数を求める) 求めたそれぞれの素数に対して、各桁の数値を回転させた数を作成し、素数かどうか調べる using System; using System.Collections.Generic; using System.Linq; class PE035 {…

Project Euler 34

C# PE

Problem 34 最大何桁まで求めたら良いのか。 [1] pry(main)> def f(n) n < 1 ? 1 : n*f(n-1) end => :f [2] pry(main)> (1..12).each { |i| puts "i:#{i} #{i*f(9)}" } i:1 362880 i:2 725760 i:3 1088640 i:4 1451520 i:5 1814400 i:6 2177280 i:7 2540160 …

Project Euler 33

C# PE

Problem 33 問題文を読んでもどうもよく理解できずすっきりしない。 xy/yz = xz となる x, y, z を求めている。 using System; class PE033 { static int Gcd(int m, int n) { int r = m % n; while (r != 0) { m = n; n = r; r = m % n; } return n; } stat…

Project Euler 32

C# PE

Problem 32 1 桁 x 4 桁、もしくは 2 桁 x 3 桁のいずれか。 1 桁 x 3 桁はありえない。9 * 999 = 8991 なので、最大でも 8 桁にしかならないから。 3 桁 x 3 桁はありえない。100 * 100 = 10000 なので、9 桁を超えてしまうから。 using System; using Syst…

Project Euler 31

C# PE

Problem 31 動的計画法の基本的な問題。 using System; class PE031 { static void Main() { int[] coins = { 1, 2, 5, 10, 20, 50, 100, 200 }; const int N = 200; int[] dp = new int[N+1]; dp[0] = 1; for (int i = 0; i < coins.Length; i++) { for (in…

Project Euler 30

C# PE

Problem 30 上限値を考える 何桁まで調べればよいのだろうか。9 の 5 乗で調べてみる。 [11] pry(main)> (1..10).each { |i| puts "i:#{i} #{9**5 * i}" } i:1 59049 i:2 118098 i:3 177147 i:4 236196 i:5 295245 i:6 354294 i:7 413343 i:8 472392 i:9 531…

Project Euler 29

C# PE

Problem 29 using System; using System.Collections.Generic; using System.Numerics; class PE029 { static void Main() { var st = new HashSet<BigInteger>(); for (int i = 2; i <= 100; i++) { BigInteger a = i; for (int j = 2; j <= 100; j++) { st.Add(BigInte</biginteger>…

Project Euler 28

C# PE

Problem 28 using System; class PE028 { static int Calc(int size) { // N x N サイズのとき、4 隅の一番大きな数字は N^2 // 4 隅の数字のうち、一番大きな数字を除いた残りの数字は // N^2 - (n - 1) * 1 // N^2 - (n - 1) * 2 // N^2 - (n - 1) * 3 // …

Project Euler 27

C# PE

Problem 27 using System; class PE027 { static bool IsPrime(int n) { if (n <= 1) return false; if (n == 2) return true; if (n % 2 == 0) return false; for (int i = 3; i*i <= n; i += 2) { if (n % i == 0) return false; } return true; } static …

Project Euler 26

PE C#

Problem 26 素直に割っていき、余りがゼロになるかまたはサイクルするまで繰り返す。 using System; using System.Collections.Generic; using System.Linq; class PE026 { static List<int> CalcRecurringCycle(int d) { var divs = new List<int>(); var mods = new </int></int>…

Project Euler 25

C# PE

Problem 25 using System; using System.Numerics; class PE025 { static void Main() { var a = new BigInteger(1); var b = new BigInteger(1); int nth = 2; while (b.ToString().Length < 1000) { var t = a + b; a = b; b = t; nth++; } Console.WriteL…

Project Euler 24

C# PE

Problem 24 using System; using System.Collections.Generic; using System.Linq; class PE024 { static long Fact(long n) { if (n == 0) return 1; else return n * Fact(n-1); } static string Calc(long n) { var ans = new List<int>(); var digits = Enume</int>…

Project Euler 23

C# PE

Problem 23 Wikipedia で、完全数、不足数、過剰数について調べる。 完全数(perfect number) その数自身を除く約数の和が、その数自身と等しい自然数のこと。 例えば 6 (= 1 + 2 + 3)、28 (= 1 + 2 + 4 + 7 + 14) や496が完全数。 不足数(deficient number) …

Project Euler 22

PE C#

Problem 22 MatchCollection と Linq を連携させるには、Cast<Match>() が必要。 Linq のメソッドチェーンで改行するさい、インデントを深くすべきか考え中。 using System; using System.IO; using System.Text.RegularExpressions; using System.Linq; class PE02</match>…

Project Euler 21

C# PE

Problem 21 d(n) の計算は、素直に割り算している。 using System; class PE021 { static int SumProperDivisors(int n) { int sum = 0; for (int i = 1; i*2 <= n; i++) { if (n % i == 0) { sum += i; } } return sum; } static int Calc() { int ans = 0;…