勉強会に参加したい方は概要を確認してください。

定期宣伝

弊社はエンジニアを熱烈募集しています．以下から気軽にカジュアル面談申し込んでください．就職・転職を考えている知人にも積極的に宣伝してください．

この勉強会の宣伝もお願いします．参加者が増えるほど質や頻度が上がると思います． #Acompany競プロ勉強会で実況や感想，質問を呟くなども．

不定期宣伝

ビッグデータや生成AIなどの最近のトレンドに関して “Trust” の文脈で考えるイベント。

6/24 新橋で開催。

たくさんの人に来て欲しいので宣伝してください。

与えられた自然数 $n$ が素数かを判定する問題を考える。

一番よく知られた素数判定法は以下のような試し割り法である。

これは「 $n$ が合成数ならその最小の素因数は $\sqrt{n}$ 以下」という性質を利用している。

def is_prime(n: int) -> bool:
    for i in range(2, math.sqrt(n) + 1):
        if n % i == 0:
            return False
    return True

計算量は $\Theta(\sqrt{n})$ 。

このアルゴリズムの入力長は $\Theta(\log n)$ であるため、これは指数時間アルゴリズムである。

2002 年に発表された、素数判定を多項式時間で行う最初のアルゴリズム。