「アルゴリズム」素数ふるい、分解素数
素数ふるい、分解素数列挙ふるい法 原始ふるい法 最適化 分解素因数 素朴アルゴリズム 最適化 Eratosthenesふるい法(エラストニふるい法) リニアふるい法(オーラふるい法)
列挙ふるい法
素数は因数が1 1 1とそれ自体の数しかないことを知っていますが、別の方法では2 2~n−1 n−1 n−1 n−1の範囲にその因数が1つもないことを意味します.
げんしふるいほう
2からn−1 n−1 n−1までの列挙
最後のcn t cnt cntは素数個数であり,pr i m e Primeが保持するのは素数である.
最適化
実際には,完全二乗数を除いて因数はペアで現れるので,i%j==0 i%j=0 i%j=0 i%j=0がループから飛び出していないと判断した場合,i%(i/j)i%(i/j)i%(i/j)i%(i/j)が0であるか否かを判断する必要がなくなり,反証法で証明する.
証明 存在i%j=0 i%j=0 i%j=0かつj>i/2 j>i/2 j>i/2
ぶんかいしつりょう
素朴なアルゴリズム
説明はしません...
最適化
もう一つ深刻な問題がありますが、私たちは本当にi i iが質量数であるかどうかを判断する必要がありますか?実は使わない
証明 はi i iが存在すると仮定し、n%i==0 n%i=0 n%i=0であり、i i iが合数0 n\%j!=0 n%j!=0了
Eratosthenesふるいほう
私たちは発見して、実は2 2 2にとって、私たちはi%2 i%2 i%2が0 0 0であるかどうかを判断し続けたが、偶数が2 2 2 2によって除去されたかどうかを判断する必要は全くない. 各素数について、その倍数はすべて合数であり、分解素数と同様に、これまでマークされていなかったすべての数は素数である
せんけいふるいほう
実は6=2∗3 6=2*3=2∗3なので、6 6 6は2回繰り返しマークされているので、いくつかの数は何度もマークされているので、発見されたすべての素数をマークします.それらのi i i i倍は合数です.
eyJ2ZXJzaW9uIjoxLjMsImZlYXR1cmVzIjp7ImxvY2F0aW9uIjp7InJvb20iOnRydWUsIm91dHNpZGUiOnRydWUsIndvcmxkIjp0cnVlfX0sInN0b3JlcyI6eyJ3b29kIjo2OTA4NCwic2NhbGVzIjo4OCwiYmFpdCI6MjI1NSwiZnVyIjoxMTg4OCwibWVhdCI6NTYyNiwidGVldGgiOjgzLCJjdXJlZCBtZWF0IjoxNzU1LCJjbG90aCI6MzEsImxlYXRoZXIiOjQ5MSwiYm9uZSBzcGVhciI6MTcsImwgYXJtb3VyIjoxLCJjaGFybSI6NywidG9yY2giOjM0LCJ3YXRlcnNraW4iOjEsInJ1Y2tzYWNrIjoxLCJjb21wYXNzIjoxLCJtZWRpY2luZSI6NCwiaXJvbiBzd29yZCI6NCwiaXJvbiI6OCwic3RlZWwgc3dvcmQiOjF9LCJjaGFyYWN0ZXIiOnsicGVya3MiOnsicHJlY2lzZSI6dHJ1ZSwiZXZhc2l2ZSI6dHJ1ZSwiYmFyYmFyaWFuIjp0cnVlfSwic3RhcnZlZCI6Mn0sImluY29tZSI6eyJnYXRoZXJlciI6eyJkZWxheSI6MTAsInN0b3JlcyI6eyJ3b29kIjowfSwidGltZUxlZnQiOjJ9LCJidWlsZGVyIjp7ImRlbGF5IjoxMCwic3RvcmVzIjp7Indvb2QiOjJ9LCJ0aW1lTGVmdCI6Mn0sImNoYXJjdXRpZXIiOnsiZGVsYXkiOjEwLCJzdG9yZXMiOnsibWVhdCI6MCwid29vZCI6MCwiY3VyZWQgbWVhdCI6MH0sInRpbWVMZWZ0IjozfSwiaHVudGVyIjp7ImRlbGF5IjoxMCwic3RvcmVzIjp7ImZ1ciI6MTEsIm1lYXQiOjExfSwidGltZUxlZnQiOjN9LCJ0cmFwcGVyIjp7ImRlbGF5IjoxMCwic3RvcmVzIjp7Im1lYXQiOi0xLCJiYWl0IjoxfSwidGltZUxlZnQiOjN9LCJ0YW5uZXIiOnsiZGVsYXkiOjEwLCJzdG9yZXMiOnsiZnVyIjowLCJsZWF0aGVyIjowfSwidGltZUxlZnQiOjN9fSwidGltZXJzIjp7fSwiZ2FtZSI6eyJidWlsZGVyIjp7ImxldmVsIjo0fSwidGVtcGVyYXR1cmUiOnsidmFsdWUiOjIsInRleHQiOiLlvojlrpzkuroifSwiZmlyZSI6eyJ2YWx1ZSI6MiwidGV4dCI6IuWGkuWHuueBq+iLlyJ9LCJidWlsZGluZ3MiOnsidHJhcCI6MTAsImNhcnQiOjEsImh1dCI6MjAsInRyYWRpbmcgcG9zdCI6MSwic21va2Vob3VzZSI6MSwibG9kZ2UiOjEsInRhbm5lcnkiOjEsIndvcmtzaG9wIjoxfSwicG9wdWxhdGlvbiI6MjMsIndvcmtlcnMiOnsiY2hhcmN1dGllciI6MCwiaHVudGVyIjoyMiwidHJhcHBlciI6MSwidGFubmVyIjowfSwib3V0c2lkZSI6eyJzZWVuRm9yZXN0Ijp0cnVlfSwid29ybGQiOnsibWFwIjpbWyIsIiwiLiIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiWSIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIl0sWyIuIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIl0sWyIuIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7Il0sWyIuIiwiLiIsIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIkYiLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIjsiLCI7IiwiOyIsIjsiLCIuIiwiLiIsIjsiLCI7IiwiOyIsIjsiLCI7Il0sWyI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIkYiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCJZIiwiLCIsIiwiLCI7IiwiOyIsIjsiLCIuIiwiLiIsIi4iLCI7IiwiLiIsIi4iLCIuIl0sWyI7IiwiOyIsIjsiLCI7IiwiLiIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiLiIsIi4iLCIuIl0sWyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCJZIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIuIiwiLiIsIjsiLCI7IiwiOyIsIjsiLCIuIiwiLiIsIi4iLCIuIl0sWyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIlkiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIkIiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIsIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiQiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIkgiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCJZIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCJGIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiQiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIjsiLCI7IiwiOyIsIi4iLCIuIiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiQiIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIjsiLCI7IiwiOyIsIi4iLCIuIiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIjsiLCI7IiwiOyIsIi4iLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiQiIsIiwiLCIsIiwiSCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiWSIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCJZIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIjsiLCI7IiwiOyIsIjsiLCJPIiwiOyIsIk8iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIkIiLCIuIiwiLiIsIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiSCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCJIIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiWSIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCJZIl0sWyIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiOyIsIiwiLCIuIiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiOyIsIiwiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIiwiLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCJPIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIjsiLCI7IiwiUCIsIiwiLCIsIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIl0sWyIuIiwiLiIsIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiTyIsIi4iLCIuIiwiViIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCI7IiwiIyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIkYiLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIl0sWyIuIiwiLiIsIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIk8iLCIsIiwiLiIsIk8iLCIuIiwiLiIsIkghIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiUCIsIiMiLCIjIiwiQSIsIkghIiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiTyIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLiIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCJJIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiTSIsIi4iLCJPIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiOyIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIjsiLCI7IiwiOyIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiViIsIi4iLCIuIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCI7IiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCJWIiwiOyIsIjsiLCIsIiwiQyIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiRiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIjsiLCI7IiwiOyIsIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiWSIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiQiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCI7IiwiOyIsIjsiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIjsiLCI7IiwiOyIsIjsiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIjsiLCI7IiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCJCIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiWSIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiSCIsIiwiLCIsIiwiLCIsIlkiXSxbIjsiLCI7IiwiLCIsIiwiLCIsIiwiWSIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiSCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCJPIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIiwiLCJZIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiSCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIk8iLCIsIiwiLCIsIlMiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIiwiLCIsIiwiLCIsIkIiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiWSIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCJZIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIlkiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCJCIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiVyIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiSCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIlkiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCJZIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIjsiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiWSIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiOyIsIjsiLCIsIiwiLCIsIiwiXSxbIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiOyIsIjsiXSxbIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCI7IiwiOyIsIjsiXSxbIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCI7IiwiOyIsIjsiXSxbIjsiLCIuIiwiLiIsIi4iLCIuIiwiLiIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLiIsIi4iLCIuIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIiwiLCIsIjsiXV0sIm1hc2siOltbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbXSxbbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlXSxbbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWVdLFtudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlXSxbbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZV0sW251bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWVdLFtudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlXSxbbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWUsdHJ1ZSx0cnVlLHRydWVdLFtudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLG51bGwsbnVsbCxudWxsLHRydWUsdHJ1ZSx0cnVlLHRydWVdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdLFtdXX0sInRoaWV2ZXMiOjIsInN0b2xlbiI6eyJ3b29kIjo0ODkwLCJmdXIiOjI0NDUsIm1lYXQiOjI0NDV9fSwicGxheVN0YXRzIjp7fSwicHJldmlvdXMiOnt9LCJjb25maWciOnsiaHlwZXJNb2RlIjp0cnVlLCJsaWdodHNPZmYiOnRydWV9LCJjb29sZG93biI6e30sImN1cmVkIG1lYXQiOjYsImNoYXJtIjowLCJ0b3JjaCI6MCwid2F0ZXJza2luIjowLCJib25lIHNwZWFyIjo1LCJydWNrc2FjayI6MCwibCBhcm1vdXIiOjAsIm1lZGljaW5lIjowLCJpcm9uIHN3b3JkIjowLCJvdXRmaXQiOnsiYm9uZSBzcGVhciI6NSwiY3VyZWQgbWVhdCI6NiwidG9yY2giOjAsImlyb24gc3dvcmQiOjAsInN0ZWVsIHN3b3JkIjowLCJsZWF0aGVyIjowLCJ0ZWV0aCI6MH0sInN0ZWVsIHN3b3JkIjowfQ==
列挙ふるい法
素数は因数が1 1 1とそれ自体の数しかないことを知っていますが、別の方法では2 2~n−1 n−1 n−1 n−1の範囲にその因数が1つもないことを意味します.
げんしふるいほう
2からn−1 n−1 n−1までの列挙
for (int i = 2; i <= n; i ++) {
bool flag = true;
for (int j = 2; j < i; j ++) {
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
Prime[++ cnt] = i;
}
}
最後のcn t cnt cntは素数個数であり,pr i m e Primeが保持するのは素数である.
最適化
実際には,完全二乗数を除いて因数はペアで現れるので,i%j==0 i%j=0 i%j=0 i%j=0がループから飛び出していないと判断した場合,i%(i/j)i%(i/j)i%(i/j)i%(i/j)が0であるか否かを判断する必要がなくなり,反証法で証明する.
証明 存在i%j=0 i%j=0 i%j=0かつj>i/2 j>i/2 j>i/2
for (int i = 2; i <= n; i ++) {
bool flag = true;
for (int j = 2; j * j <= i; j ++) { // ，
if (i % j == 0) {
flag = false;
break;
}
}
if (flag) {
Prime[++ cnt] = i;
}
}
ぶんかいしつりょう
素朴なアルゴリズム
説明はしません...
for (int i = 2; i <= n; i ++) {
if (n % i == 0) {
bool flag = true;
for (int j = 2; j < i; j ++) {
if (i % j == 0) {
flag = false;
break;
}
}
while (n % i == 0 && flag) {
n /= i;
Prime[++ cnt] = i;
}
}
}
最適化
もう一つ深刻な問題がありますが、私たちは本当にi i iが質量数であるかどうかを判断する必要がありますか?実は使わない
証明 はi i iが存在すると仮定し、n%i==0 n%i=0 n%i=0であり、i i iが合数0 n\%j!=0 n%j!=0了
for (int i = 2; i <= n; i ++) {
while (n % i == 0) {
Prime[++ cnt] = i;
n /= i;
}
}
Eratosthenesふるいほう
私たちは発見して、実は2 2 2にとって、私たちはi%2 i%2 i%2が0 0 0であるかどうかを判断し続けたが、偶数が2 2 2 2によって除去されたかどうかを判断する必要は全くない. 各素数について、その倍数はすべて合数であり、分解素数と同様に、これまでマークされていなかったすべての数は素数である
void Eratosthenes_sieve() {
for (int i = 2; i <= n; i ++) {
if (flag[i]) continue; //
Prime[++ cnt] = i;
for (int j = i; j <= n / i; j ++) {
flag[j * i] = true;
}
}
}
せんけいふるいほう
実は6=2∗3 6=2*3=2∗3なので、6 6 6は2回繰り返しマークされているので、いくつかの数は何度もマークされているので、発見されたすべての素数をマークします.それらのi i i i倍は合数です.
void line_sieve(int n) {
for (int i = 2; i <= n; i ++) {
if (!flag[i]) {
Prime[++ cnt] = i;
}
for (int j = 1; j <= cnt && Prime[j] * i <= n; j ++) {
flag[i * Prime[j]] = true;
if(i % Prime[j] == 0) {
break;
}
}
}
}