素数列挙について - MugiCha
Competitive Programming Advent Calendar 3日目は、数学っぽい話をしたいと思います。 N以下の素数をすべて求めよ。 N以下の素数の個数を求めよ。 A以上B以下の素数の個数を求めよ。 こんな感じの問題を見たことがあると思います。また問題としてでなくても、解く過程にこのようなサブ問題を解かなければいけない場合もよくあると思います。素数については説明しなくてもいいですよね？ このような問題を素数列挙と呼ぶことにします。素数列挙ができれば、大きい数の素数判定や素因数分解をめっちゃ高速化したり、トーティエント関数、メビウス関数等、数学系のいろんな関数を求めたりできます。最近のもので素数列挙がほぼ必須のものだと Codeforces Beta Round #86 (Div. 1 Only) C. Double Happiness ICPC 国内予選 2011 A
[ruby-list:16645] Re: Sieve of Eratosthenes (Re: [ruby-dev:6094])
Subject: [ruby-list:16645] Re: Sieve of Eratosthenes (Re: [ruby-dev:6094]) From: wakou@ i t r p Date: Thu, 9 Sep 1999 07:30:38 +0900 In-reply-to: 12994 青山です。 On Thu, 18 Mar 1999 17:21:54 +0900, Shin-ichiro Hara <sinara / blade.nagaokaut.ac.jp> wrote: > するとある程度 max が大きいと(稲葉1)の大体３倍のスピード > が出るようです。 ちょっと古い話しですが、NIFTY の方でこの話が出まして、少し手を加えた所、 max が大きい場合、さらに倍ぐらいになりました。これでほぼ awk, perl の 速度に追い付いたようです。 max =
フェルマーテストによる素数判定
最近の主な更新 2005-11-25 - 細かな修正 2005-11-22 - 第二版 2004-09-12 - 初版 概要 本稿では，確率的素数判定法の一つであるフェルマーテストについて述べる． 1章ではフェルマーテストの理論的基礎であるフェルマーの小定理を導く．2章 では，フェルマーテストの Python による実装を与える．3章では，フェルマー テストによる素数判定が誤る原因となる，擬素数の存在について述べる． 1 フェルマーの小定理 フェルマーテストの準備として，以下ではフェルマーの小定理とよばれる定理 を導く．まず，次の補題が成り立つ． 補題 1.1 素数 p と 自然数 r （0 < r < p）に対し， pCr = p! / (r!(p-r)!) ≡ 0 (mod p) が成り立つ． 証明 p! は p で割りきれる．一方，r!(p-r)! は p よりも小さい自然 数の，複
The Prime Pages
What are the PrimePages? Webster's New Collegiate Dictionary defines prime as follows. prime \'prīm\ n [ME, fr. MF, fem. of prin first, L primus; akin to L prior] 1 : first in time : ORIGINAL 2 a : having no factor except itself and one <3 is a ~ number> b : having no common factor except one <12 and 25 are relatively ~> 3 a : first in rank, authority or significance : PRINCIPALb : having the high
多項式時間素数判定アルゴリズム
ＡＫＳアルゴリズムと PRIMES is in Pに関する解説のページです 以下の説明は、元論文を参照しながらお読みください。 元論分のサイト：Manindra Agrawal, Neeraj Kayal and Nitin Saxena, PRIMES is in P, the original version of the paper. アルゴリズムの基本となるアイデア アルゴリズムの概要 AKS アルゴリズム 使用する用語と記号 アルゴリズムの動作概要 アルゴリズムの正当性の証明概要 アルゴリズムの正当性の証明の蛇足説明 アルゴリズムの正当性の証明詳細のための準備 PRIMES is in P セクション３の解説 Lemma 3.1. Lemma 3.1.(fact 1) Lemma 3.1.(fact 2) Lemma 3.1.(fact 3) Lemma 3.1.(fact 4
100万までの素数表
100万までの素数表 この素数表は、100万までの素数を検索できるのはむろんのこと、表組みや区切り記号を使わず に素数を表示しています。したがって、カットアンドペーストにより、100万までの数であれば任 意区間の素数表を簡単につくることができます。むろん100万までの 78498個の素数をすべて切り 取ることも可能です。その際のファイルサイズは630kバイトほどになります。 また、この素数表をファイルに落としておくと、簡単なアルゴリズムで一兆（！）までの素数表 をつくることができます。その際は、ファイルサイズが非常に大きくなるのでデータを圧縮保存す ることが必要になります。 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 14
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
On Lucas's Test For The Primality of Mersenne's Numbers
http://members.just-size.net/prime/
試行除算による素数判定