ひとりで勝手にはじめた蟻本読書会 数学的な問題 線分上の格子点の個数 ユークリッドの互除法 蟻本読書会 の続きです。
素数判定
N が素数のときは YES、そうでないときは NO と一行に出力せよ。
入力されるデータ
N(ただし、17 ≦ N ≦ 1,000,000)
「俺」は怪しい宗教団体「素数の光」に洗脳されかかっているようです。
素数は約数が 2 つしか存在しない自然数のことです。1 とその数以外では割り切ることができないので、それ以外に割り切ることができる数があるか探してみます。このとき全部探していると時間がかかるので、省略できるものがないか考えてみます。
まず 2 以外の偶数は素数ではありません。
与えられた数を割り切ることができる数を探すのですが、2 で割り切ることができるか調べたあとは奇数のみを試します（4 とか 6 で割るのはやるだけ無駄）。
また 101 が素数であるかどうかを考えるときに 11 で割り切ることができないことが確認できます。11 で割ったときの商は 9 です。そのためもし 101 を割り切ることができる 101 以外の数が見つかったとしたらそれは 11 よりも小さな数になります。だったらすでに見つかっていないとおかしいので、11 で割り切ることができないことが確認された段階で 101 は素数であることがわかります。与えられた数の平方根を切り上げた数まで試してみて、割り切ることができないならそれは素数です。
この方法だと N が 1,000,000 程度であればすぐに素数かどうか判定できます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
using System; using System.Collections.Generic; using System.Linq; class Program { static bool IsPrime(int n) { if (n <= 1) // 1 は素数ではない。それ以下の整数は問題外 return false; if (n == 2 || n == 3) // 2 と 3 は素数である return true; if (n % 2 == 0) // 2 以外の偶数は素数ではない return false; // 3 以上の奇数で N の平方根を切り上げた数まで試してみる // これで割り切ることができる数が見つからないなら素数である int max = (int)Math.Ceiling(Math.Sqrt(n)); for (int i = 3; i <= max; i += 2) { if (n % i == 0) return false; } return true; } static void Main() { int N = int.Parse(Console.ReadLine()); if(IsPrime(N)) Console.WriteLine("YES"); else Console.WriteLine("NO"); } } |
約数の数と素因数分解
整数 N が与えられます。 N! の正の約数の個数を 10^9 + 7 で割った余りを求めてください。
入力されるデータ
N（ただし 1 ≦ N ≦ 1,000）
約数の数は素因数分解したあと、それぞれの素因数の指数（右肩の数字）に 1 を足したものを掛け合わせることで求めることができます。
素因数分解は 2 から順番に割り切れるかどうかを試していき、割り切れたらまた同じ数で試します。そしてそれぞれの成功した回数を数えればよいです。N! は積の形になっているので、それぞれを割り切る数があるか調べます。
2 で割れるか試したあと、4 とか 6 のような素数ではない数でも割り切れるか試すことになりますが、すでにそれより小さな数で割られているため、非素数を数えてしまうようなことはありません。
factors という配列を定義し、例えば 2 で割り切れるなら factors[2] をインクリメントします。最後に要素が 0 ではない要素だけを集めてそれに 1 を加えたものを掛け合わせて解を求めます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = int.Parse(Console.ReadLine()); List<int> list = new List<int>(); for (int i = 1; i <= N; i++) list.Add(i); // list に格納した 1 ～ N までの数を割り切ることができる数と、その回数を数える int[] factors = new int[N + 1]; for (int i = 2; i <= N; i++) { for (int index = 0; index < N; index++) { while(list[index] % i == 0) { list[index] /= i; factors[i]++; } } } // 1回以上使われている素因数のみ集める factors = factors.Where(_ => _ > 0).ToArray(); long ans = 1; foreach (int factor in factors) { ans *= factor + 1; ans %= 1000000007; // 10^9 + 7 で割った余りを求めよとあるので } Console.WriteLine(ans); } } |
素数の個数とエラトステネスの篩
エラトステネスの篩 (ふるい) は、指定された整数以下のすべての素数を発見するための単純なアルゴリズムです。古代ギリシアの科学者、エラトステネスが考案したとされます。
1 ～ n までの数字を書く
1 は素数ではないので消す
残った数のなかで最小の 2 は素数。それ以外の 2 の倍数は素数ではないので消す。
残った数のなかで次に最小の 3 は素数。それ以外の 3 の倍数は素数ではないので消す。
残った数のなかで次に最小の 5 は素数。それ以外の 5 の倍数は素数ではないので消す。
これを繰り返すと最終的に素数のみが残る。
篩い落とし操作は n の平方根 まででよい。
これだと n の平方根 より大きな素数による合成数が消えないが、これは n よりも大きな値となるので。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N = 122; bool[] isPrimes = GetIsPrimes(N); for (int i = 0; i < isPrimes.Length; i++) { if (isPrimes[i]) Console.WriteLine(i); } } static bool[] GetIsPrimes(int n) { bool[] isPrimes = new bool[n + 1]; for (int i = 0; i < isPrimes.Length; i++) isPrimes[i] = true; isPrimes[0] = false; isPrimes[1] = false; int max = (int)Math.Ceiling(Math.Sqrt(n)); for (int i = 0; i <= max; i++) { if (isPrimes[i]) { int k = 2; while (true) { if (i * k < isPrimes.Length) isPrimes[i * k] = false; else break; k++; } } } return isPrimes; } } |
自然数 n が与えられるので、n よりも小さい素数の数は何個存在するかを求めてください。
入力されるデータ
n
（ただし、1 ≦ n ≦ 10,000 )
エラトステネスの篩で i が素数かどうかの結果を 配列 isPrimes で取得しておきます。あとは配列内の true の個数を出力するだけです。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
using System; using System.Collections.Generic; using System.Linq; class Program { // GetIsPrimes メソッドは同じなので省略 static void Main() { int N = int.Parse(Console.ReadLine()); if (N == 1) { // GetIsPrimes は引数が 1 以上でないと例外が発生する Console.WriteLine(0); } else { // 与えられた数ではなくそれより小さいものの素数の数を問われているので bool[] isPrimes = GetIsPrimes(N - 1); Console.WriteLine(isPrimes.Count(_ => _ == true)); } } } |
「N も (N+1)÷2 も素数」を満たす奇数 N を 2017に似た数 とします。
Q 個のクエリが与えられます。
クエリ i(1 ≦ i ≦ Q) では奇数 l_i ,r_i が与えられるので、l_i ≦ x ≦ r_i かつ 2017に似た数 となる奇数 x の個数を求めてください。
入力されるデータ
Q
l_1 r_1
l_2 r_2
…
l_Q r_Q（ただし、1 ≦ Q ≦ 10^5
1 ≦ l_i, r_i ≦10^5
l_i, r_i は奇数）
エラトステネスの篩で i が素数かどうかの結果を 配列 isPrimes1 で取得し、そこから i が 2017 に似た数の定義に当てはまっているか判断して結果を isPrimes2 に格納します。
クエリが何度も飛んで来るので累積和の手法で対応します。配列 sums に i 以下であるとき isPrimes2 がtrueである個数を格納しておけば、sums[r] – sums[l – 1] を計算することで 区間[l, r] における isPrimes2 がtrueである個数を高速に求めることができます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
using System; using System.Collections.Generic; using System.Linq; class Program { // GetIsPrimes メソッドは同じなので省略 static void Main() { int max = 100010; // 1 ≦ l_i, r_i ≦10^5 なのでそれよりも少し大きな数 bool[] isPrimes1 = GetIsPrimes(100010); bool[] isPrimes2 = new bool[100010]; for (int i = 0; i < max; i++) { if (isPrimes1[i] && isPrimes1[(i + 1) / 2]) isPrimes2[i] = true; } // sums[n] : 0 ≦ i ≦ n の isPrimes2[i] である個数 int[] sums = new int[max]; for (int i = 1; i < max; i++) { sums[i] = sums[i - 1]; if (isPrimes2[i]) sums[i]++; } // クエリが何度も飛んで来るので累積和の手法で・・・ int Q = int.Parse(Console.ReadLine()); List<int> rets = new List<int>(); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int l = vs[0]; int r = vs[1]; rets.Add(sums[r] - sums[l - 1]); } foreach(int ret in rets) Console.WriteLine(ret); } } |
エラトステネスの区間篩
値が大きくなるとエラトステネスの篩で N 以下の素数をすべて求めるのは現実的ではなくなります。N が 10の12乗のような大きな数の場合、どうすればいいのでしょうか？
N が合成数ならば、√N 以下の素数 p が存在し、これで割り切れる
これに気がつけば √N 以下の素数 p の倍数をふるい落とせば十分であることに気がつきます。10の12乗だと大きすぎて処理ができませんが、√（10の12乗）となると10の6乗であり、処理が可能となります。
以下のコードは 999999990000 から 1000000000000 までの素数の数を求めています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { long a = 999999990000; long b = 1000000000000; int n = (int)Math.Ceiling(Math.Sqrt(b)); bool[] isPrimes1 = GetIsPrimes(n); // a 以上 b 以下の整数 i が素数かどうかは isPrime2[i - a] に格納される bool[] isPrimes2 = new bool[b - a + 1]; for (int i = 0; i < isPrimes2.Length; i++) isPrimes2[i] = true; for (int i = 0; i < isPrimes1.Length; i++) { if (!isPrimes1[i]) continue; // a 以上の i の倍数（ただし k は 2 以上）を消していく long k = a / i; // k の初期値 while (true) { if (i * k <= b) { if (k > 1 && i * k - a >= 0) isPrimes2[i * k - a] = false; } else break; k++; } } Console.WriteLine(isPrimes2.Count(_ => _ == true)); } } |
