C++

コピー省略（Copy Elision）は「コピーの省略」とも呼ばれる、コンパイラが行う最適化技術の一つです。オブジェクトの不要なコピーを回避することで、プログラムの実行効率を向上させます。現在の主要なC++コンパイラのほとんどが、この最適化技術を採用しています。また、関数の戻り値に対して同様の最適化を適用する仕組みは、RVO（Return Value Optimization：戻り値の最適化）と呼ばれます。それでは、サンプルコードを使って、コピー省略がどのように動作するのかを見ていきましょう。サンプルコード#include <iostream> using namespace st

本記事では、指定された範囲内の素数を生成するために「アトキンの篩（Sieve of Atkin）」を実装したC++プログラムを紹介します。アトキンの篩は、指定した整数までのすべての素数を求めるための現代的なアルゴリズムで、古典的なエラトステネスの篩と比べて理論上はより高速に動作することが知られています。 アルゴリズム 開始 結果リストを作成し、2・3・5を格納する ふるい配列（sieve）をfalseで初期化する 以下の条件a〜cのいずれかを満たす場合、sieve[n]をtrueにマークする a) n = (4*x*x) + (y*y) の解の個数が奇数 かつ

本記事では、セグメント篩（Segmented Sieve）を用いて、指定された範囲内の素数を効率的に生成するC++プログラムを紹介します。セグメント篩は、まず単純なエラトステネスの篩（Simple Sieve）を使って √(high) 以下の素数をすべて求めます。その後、対象となる範囲 [low, high] を小さな区間（セグメント）に分割し、各セグメントごとに素数を順番に計算していくというのが基本的なアイデアです。この手法の利点は、範囲全体に対するブール配列を一度に確保する必要がないため、メモリ使用量を大幅に削減できる点にあります。特に大きな数値範囲を扱う場合に有効です。アルゴリズムの手順

GCCでコンパイルを行う際、「undefined reference（未定義参照）」といったリンクエラーが、ライブラリを指定する順序によって発生したり消えたりすることがあります。これはコンパイラ本体の問題ではなく、リンカ（ld）のデフォルトの動作に起因するものです。 リンカは「必要になった時点」でしかアーカイブを読み込まない リンカは、コマンドラインで渡されたファイルを基本的に左から右へ順番に処理します。アーカイブライブラリ（.a ファイル）に対しては、「その時点で未解決になっているシンボル」を満たすメンバーだけを取り込むのがデフォルトの挙動です。 重要なのは、リンカが一度読み飛ばしたシンボ

C++には4種類のキャスト演算子(static_cast、dynamic_cast、const_cast、reinterpret_cast)が用意されています。それぞれ目的と安全性が異なるため、状況に応じた適切な使い分けが重要です。本記事では、各キャストの役割と使用場面をわかりやすく解説します。 const_cast：const性の追加・削除 const_castは、変数に対してconst修飾子を付けたり外したりするためのキャストです。const指定されたオブジェクトへの参照やポインタを受け取ったものの、内部でconstではない操作を行う必要がある場合などに活用できます。 ただし、本来cons

<bits/stdc++.h>とは何か #include <bits/stdc++.h>は、C++の標準ライブラリを一括で読み込めるヘッダーファイルです。このファイルを1つインクルードするだけで、標準ライブラリのほぼすべての機能が利用できるようになります。そのため、競技プログラミングのコンテストなど、解答にかける時間を少しでも節約したい場面では重宝されることがあります。 ソフトウェア開発では避けるべき理由 しかし、ソフトウェア工学の観点からは、インクルードするファイルは必要最小限に抑えることが良い設計とされています。このヘッダーファイルを使うと、プログラムにとって実際

C/C++プログラミングにおいて、ヘッダーファイルを読み込む際に使われる#includeディレクティブには、#include <filename>と#include filenameという2つの記述形式があります。一見似ているこの2つですが、その違いはプリプロセッサがインクルード対象のファイルを検索する場所にあります。#include <filename> の場合山括弧（< >）で囲んだ形式では、プリプロセッサは実装依存の方法でファイルを検索します。具体的には、コンパイラがあらかじめ設定している標準インクルードディレクトリ（システムのヘッダーファイルが格納さ

ラビン・ミラー素数性テスト（Rabin–Miller Primality Test）は、与えられた整数が素数であるかどうかを判定するための確率的アルゴリズムです。フェルマーの素数判定法やソロベイ・シュトラッセン・テストと同様の形式を持ち、この手法の原型はロシアの数学者 M. M. Artjuhov によって考案されました。このテストは、反復回数を増やすことで誤判定の確率を極めて低く抑えられるため、巨大な整数に対しても高速に素数判定が可能であり、暗号技術などの分野で広く活用されています。アルゴリズム本実装の中核となるのは、次の3つの関数です。1. mulmod：モジュロ乗算(a × b) mod

本記事では、複数の整数からGCD（最大公約数）とLCM（最小公倍数）を求めるC++プログラムを解説します。GCD（Greatest Common Divisor：最大公約数）とは、2つ以上の整数（すべてがゼロではないもの）に共通する約数の中で最大となる正の整数のことです。英語では Greatest Common Factor（最大公因子）とも呼ばれます。一方、LCM（Least Common Multiple：最小公倍数）とは、2つの数のどちらの倍数にもなる数のうち、ゼロ以外で最小の数を指します。アルゴリズムまず、処理の流れを擬似コードで確認しましょう。GCDの計算には、剰余を繰り返し求める「

本記事では、サンダラムのふるい（Sieve of Sundaram）を実装し、指定した範囲までの素数を生成するC++プログラムを紹介します。サンダラムのふるいは、1934年にインドの数学者S.P.サンダラムによって発見された素数生成アルゴリズムです。サンダラムのふるいとはサンダラムのふるいは、エラトステネスのふるいと同様に素数を求めるアルゴリズムですが、奇数のみを扱うことで効率化を図っています。n未満の素数を求める際は、まず (n−2)/2 のサイズの配列を用意し、「i + j + 2ij」（1 ≤ i ≤ j）の形で表される数値を順にマークしていきます。最終的にマークされていないインデックス

フェルマー素数判定テスト（Fermat Primality Test）は、与えられた整数が素数かどうかを確率的に判定するための古典的な手法です。本記事では、このアルゴリズムの仕組みと、C++による実装コードをわかりやすく解説します。 フェルマーの小定理の基本 フェルマー素数判定は「フェルマーの小定理」に基づいています。p を素数、a を p の倍数でない任意の整数とすると、次の関係が常に成り立ちます。 ap−1 ≡ 1 (mod p) この性質を利用し、判定したい数 n に対してランダムな底 a を選び、an−1 mod n が 1 と一致するかを確認します。一致しなければ n は確実に合成数

ブース(Booth)の乗算アルゴリズムは、2の補数表現で表された2つの符号付き2進数を乗算するためのアルゴリズムです。考案者のブース氏は、当時のデスクトップ電卓が加算よりもシフト演算の方が高速に処理できることに着目し、計算速度を向上させるためにこの手法を編み出しました。本記事では、このアルゴリズムの考え方と、C++による実装例をわかりやすく解説します。 アルゴリズムの流れ 被乗数をBRレジスタに、乗数をQRレジスタに格納し、乗数の最下位ビットQnとその隣のビットQn+1の組み合わせに応じて、以下の操作を繰り返します。 Begin 被乗数をBRへ、乗数をQRへ格納する 以下の条件

Schönhage-Strassenアルゴリズムとは Schönhage-Strassen（ショーンハーゲ・シュトラッセン）アルゴリズムは、2つの数値を乗算するために用いられるアルゴリズムです。非常に大きな整数の乗算において漸近的に高速に動作することで知られており、実際には 2215〜2217（10進数で約10,000〜40,000桁）を超えるような巨大な数値を扱う場合に、Karatsuba法やToom-Cook法といった従来の乗算手法を上回る性能を発揮し始めます。 アルゴリズムの流れ この実装では、次の3つのステップで乗算を行います。 1. 桁数のカウント 関数 noOfDigit() を

ロシアン・ピーザント法（Russian Peasant Algorithm、通称「ロシア農民の掛け算」）は、2つの数値の積を高速に計算するためのアルゴリズムです。大きな数同士の乗算でも、シフト演算と加算だけで効率よく処理できる点が大きな特徴です。アルゴリズム基本的な流れは以下のとおりです。開始 RussianPeasant(num1, num2) result = 0 while (num2 > 0) if (num2 の最下位ビットが 1) result = result + num1 num1 を左に1ビ

本記事では、オイラーの定理に基づいてモジュラ乗法逆元（modular multiplicative inverse）を求めるC++プログラムを紹介します。モジュラ乗法逆元が存在するためには、対象となる数と法（modular value）が互いに素である必要があります。モジュラ乗法逆元とは整数 a の法 m におけるモジュラ乗法逆元とは、次の式を満たす整数 x のことです。(a * x) % m = 1このような x が存在するのは、a と m の最大公約数が1（つまり互いに素）の場合のみです。オイラーの定理を利用すると、効率的に逆元を計算できます。アルゴリズム以下の手順で、1から入力値までの各

拡張ユークリッドの互除法(Extended Euclidean Algorithm)は、2つの整数の最大公約数(GCD)を求めるためのもう一つの手法です。通常のユークリッドの互除法と異なり、ベズーの等式 ax + by = gcd(a, b) を満たす係数 x と y を同時に求められる点が大きな特徴です。モジュラ逆数の計算などへの応用も可能で、コンピュータプログラムにおいて非常に効率的な手法として知られています。 アルゴリズムの流れ 拡張ユークリッドの互除法は、再帰呼び出しを利用して以下の手順で実装します。 開始 変数 a、b、x、y を宣言する gcdExtended(int

フェルマーの小定理は、初等整数論における最も基本的な結果の一つであり、フェルマー素数判定法の理論的基礎となっています。この定理は、1640年に提唱したフランスの数学者ピエール・ド・フェルマーにちなんで名付けられました。定理の内容は次のとおりです。p が素数であるとき、任意の整数 a に対して、ap − a は必ず p の整数倍になるというものです。特に a が p で割り切れない場合は、ap−1 ≡ 1 (mod p) が成り立ちます。この性質を応用すると、m が素数であり、かつ a と m が互いに素である場合、a のモジュラー逆元（m を法とする乗法逆元）は am−2 mod m として効

0-1ナップサック問題とは、それぞれに「重み」と「価値」が設定された複数のアイテムが与えられたとき、ナップサックの容量（許容される総重量）を超えない範囲で、アイテムを選んで合計価値を最大化するという古典的な最適化問題です。各アイテムは「入れるか・入れないか」の2択しかないため、「0-1」と呼ばれます。この記事では、C++を使って0-1ナップサック問題を再帰的に解くプログラムを紹介します。入力データValue = [10, 20, 30, 40, 60, 70] Weight = [1, 2, 3, 6, 7, 4] int w = 7出力結果knapsack value is: 100アルゴリ

フラクショナルナップサック問題とは？ フラクショナルナップサック問題（Fractional Knapsack Problem）は、それぞれ重み（weight）と価値（value）を持つ複数の品物が与えられ、容量が限られたナップサックに品物を詰め込んで、合計価値を最大化することを目指す古典的な最適化問題です。 この問題の大きな特徴は、品物を途中で分割して詰められるという点です。品物が「全部入れるか、入れないか」の二択しかない0/1ナップサック問題とは異なり、フラクショナル版では「半分だけ入れる」という扱いが許されます。そのため、貪欲法（Greedy Approach）を用いることで、常に最適解を

本記事では、与えられた正の整数 n を正の整数の和として表現する、すべての一意な分割（パーティション）を生成する C++ プログラムを紹介します。例えば 4 という整数は、「4」「3 + 1」「2 + 2」「2 + 1 + 1」「1 + 1 + 1 + 1」のように、複数の組み合わせで表すことができます。このプログラムは、そのような組み合わせを重複なくすべて出力します。 アルゴリズムの考え方 基本的な戦略は「最初に最大の要素だけからなる分割から始め、規則的に次の分割を生成していく」というものです。擬似コードで示すと以下のようになります。 開始 　　関数 displayAllUniquePart