問題タブ [number-theory]

重複の可能性:
特定の数までの R の素数のリストを生成する

R言語で指定された範囲内のすべての素数を見つけるエレガントな方法は何ですか?

約数が与えられると、最初の三角形の数を見つける必要があります。

三角形数は自然数の和と同じです。

私は2から始まる素数を取り、生成された数が三角形の数と一致するようにそれらを並べ替える方法を採用していました。

たとえば、5 つの約数が与えられたとします。2 以降の素数を として取り(2,3,5)ますN=p1^a1*p2*a2*p3^a3。(a1+1)(a2+1)....ここにある除数の数は2,3,5べき乗と順列を取ることができます。次にn^2+n=2k（kは順列から得られた値です）。n 値が整数であることを確認します。

これ以外に効率的なアルゴリズムは見つかりませんでした。より最適なアルゴリズムはありますか?

エラトステネスのふるいを実装する素数ジェネレーターを作成しようとしています。ただし、出力にはいくつかの合成数 (25、49、およびその他の 5 と 7 の倍数など) が含まれます。

これが私のコードです：

これが出力です....

/blockquote>

1 2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97

私の先生は私たちに数学の問題についてのacmの問題を与えました。試しましたが、TLEを入手しました。

ここに問題があります。

オイラーのトーティエント関数φ（n）[ファイ関数と呼ばれることもあります]は、nに対して互いに素であるn未満の数の数を決定するために使用されます。たとえば、1、2、4、5、7、および8はすべて9未満であり、互いに素であるため、φ（9）=6です。HGはXYのマスターです。ある日、HGは数学ゲームによってオイラーのトーティエント関数についてXYに何かを教えたいと思っています。つまり、HGは正の整数Nを与え、XYはマスターに2 <= n <= Nの値を伝えます。この値のφ（n）は最大です。すぐにHGは、これがループスの入門者であるXYにとっては少し簡単に思えることに気づきます。なぜなら、XYは小さなプログラムで非常に速く正しい答えを出すからです。したがって、HGはいくつかの変更を行います。今回、XYは、n/φ（n）が最大である2 <= n<=Nの値を彼に伝えます。今回、XYはこの問題を解決するのに十分な知識を持っていないため、いくつかの困難に直面します。

入力T個のテストケースがあります（1 <= T <= 50000）。各テストケースについて、標準入力には2≤n≤10^100の行が含まれています。

出力テストケースごとに、上記の質問に答える1行の出力が必要です。

サンプル入力210100

サンプル出力630

これが私のコードです。誰かがそれを改善するのを手伝うことができますか？

数Nが与えられた場合、i>=1およびi<=Nであるすべてのiの約数の数を見つける必要があります。理解できません。素因数分解を使用してこれを行う必要がありますか？制限はN<=10 ^ 9です。サンプル出力：

関数から複数の値を返すことができるかどうかに興味があります。たとえば、拡張ユークリッド アルゴリズムなどの関数を考えてみましょう。基本的なステップは、この Input is 非負の整数 a および b によって記述されます。出力は、 のようなトリプレット (d、i、j) ですd=gcd(a,b)=i*a+j*b。私の質問の目標を明確にするために、短い再帰コードを書きます。

r を次のようにします。 a=r*b+q;

トリプレットを返すにはどうすればよいですか?

正の整数が与えられたとき、 となる4つの整数、、をm見つけます。余分なスペースを使用できます。abcda^2 + b^2 + c^2 + d^2 = mO(m^2 log m)

私は解決策を考えることができますが、O(m^3)解決策について混乱していO(m^2 logm)ます..

2つの整数が与えられた場合、それらの最大の合同係数を見つける簡単な方法はありますか？つまり、a％n == b％n、またはそれらすべてを列挙することさえできますか？明らかに、私はそれらよりも小さいすべての値を試すことができましたが、もっと簡単な方法があるはずです。

私はgcdsで何かをしようとしましたが、％n == b％n == 0であることがわかります。これは、私が望んでいたほどクールではありません。これは必ずしも最大のn。

何か案は？

次のコードは私に奇妙なエラーを示しています

そして、私は何を意味するのか理解できませんでした、誰かが私を助けることができますか？

http://en.wikipedia.org/wiki/Binary_GCD_algorithm

このウィキペディアのエントリには、非常に不満足な含意があります。バイナリ GCD アルゴリズムは、標準のユークリッド アルゴリズムよりも 60% も効率的でした。コンピュータ。

さて、さらに 15 年が経過しました... これらの 2 つのアルゴリズムは、今日のハードウェアの進歩とどのように重なり合っているのでしょうか?

バイナリ GCD は、低レベル言語では引き続きユークリッド アルゴリズムよりも優れていますが、Java などの高レベル言語ではその複雑さのために遅れをとっていますか? それとも、現代のコンピューティングではその違いは意味がありませんか?

なぜ私はあなたが尋ねるかもしれないことを気にしますか？今日、たまたま 1,000 億個の処理をしなければなりません :) コンピューティングの時代 (かわいそうな Euclid) に乾杯します。