あけましておめでとうございます。
昨年中はたくさんのご愛顧をいただきありがとうございました。 本年は2017年卒としての就職が決まりいままでと違う環境へ見切り発車いたします(ﾊﾟｿｺﾝｶﾀｶﾀｵﾀｸができれば嬉しい)。 就職先に関してはSNS等からRECONして下さい!!! 本年も、昨年と変わらぬご愛顧のほどよろしくお願い申し上げます。
2017年から30年後の君へ
2017年は素数の年
素数は"1"と自分の数でしか割ることのできない孤独の数字です。そして、今年2017年は2011年以来5年ぶりの素数の年です。しかし、人は孤独な素数が好きだ暗号や乱数の生成とかで使いますね…。原子的な素数の判断といえば「エラトステネスのふるい」です。しかし、大きな数では無限に時間がかかります。大きな数字でも「フェルマーの小定理」を用いれば素数を判断することが出来ます。
「エラトステネスのふるい」とは
1以外の倍数を順次除き残ったものが素数であるとするものです。
1つずつふるいをかける…。
def is_prime(q): i = 2 while i <=q: if q % i == 0: return False i += 1 return True is_prime(2017) True is_prime(2047) False
「フェルマーの小定理」とは
ap-1 mod p の答えが1以外ならpは合成数である。ただし、aとpが素の関係（最大公約数が1)であること。 もっと単純化するとaに2を代入してqが素数なら答えが1になるということです。
フェルマーの小定理
def is_prime(q): q = abs(q) if q == 2: return True if q < 2 or q&1 == 0: return False return pow(2, q-1, q) == 1 is_prime(2017) True is_prime(2047) True
2047は素数?合成数?
お手軽＆高速なフェルマーの小定理です。 しかし、これが、真実とは限りません。重大な欠陥があります。 真実を知るための素因数分解
素因数分解
def prime_is(q): i = 2 table = [] while i * i <= q: while q % i == 0: q /= i table.append(i) i += 1 if q > 1: table.append(q) return table prime_is(2047) [23, 89]
素因数が求まってしまいました…。
23と89を掛けると2047ですね♥
じつは、たまに素数じゃない数もTrueとして通ってしまいます。
フェルマーの小定理の例外である。合成数を「疑素数」といいます。社会のハミ出しモノの皆様のようですね!!!
さいごに
2017年はこのネタで女子との話題に困ったらこの話をしましょう!!!そして、末永く付き合い30年後の「2047年」君にまた同じ話をしましょう。さようなら!!!
参考
2017_Fermat_little_theorem.py · GitHub
