問題タブ [prime-factoring]

Pollard の rho アルゴリズムを使用して素因数分解を計算しようとして、どこが間違っているのかわかりません。

シュノール群生成子を見つけるには、次のような 3 つの数 p、q、r を見つける必要があります。

• p = qr + 1
• p と q は素数

p と q が非常に大きな素数でなければならない場合、すべての基準を満たす q と r を見つけることは非常に困難です。GNU GMP ライブラリを使用して q と r をランダムに見つけようとしましたが、ラップトップで 30 分間見つけた数字で上記の基準を満たすものはありませんでした。

そのような数とショール群ジェネレーターを見つけるための高速な方法はありますか?

ありがとう！

Sundaram のふるい ( wiki )について説明してくれる人が必要です。配列に整数(41,43,47,49,51,53,59)のリストがあるとします。

上記のウィキペディアの説明では、次のことが言及されています。

奇数の整数は、それが 2(i+j+2ij)+1 の形式である場合にのみ、最終的なリストから除外されます。

*。プログラム（できればVBA）でこれを達成する方法を理解しようとしています。出力が(41,43,47,53,59)になるようにします。

説明をよろしくお願いします。

よろしく、

重複の可能性:
素数部分としての数値

私はこの宿題を持っています。地獄のように大変で、与えられた数の個別の素数分割をすべて取得する必要があります。たとえば、番号 7 には 5 つの異なる主要なパーティション (または、2 つの主要なパーティションを表す 5 つの異なる方法) があります。

• 5 + 2
• 2 + 5
• 3 + 2 + 2
• 2 + 3 + 2
• 2 + 2 + 3

ご覧のとおり、素数の場合、数値自体は除外されます。すべての個別のパーティションを印刷する必要はなく、それらの数だけを印刷する必要があります。

だから私はこれで少し迷っています。私はまったくコードを作成できませんでしたが、動的プログラミングのような観点からアプローチする必要があると思います。私はいくつかのヒントを求めているだけです。誰かがアイデアを持っていますか？前もって感謝します。

最大入力数は 100 です。また、プログラムの実行時間は 1 秒を超えることはできず、メモリ制限は 128 MB です。

因子を見つけてから各因子が素数であるかどうかを確認する代わりに、エラトステネスの篩を使用して数値の素因数を出力しようとしています。

Xcodeで実行しても、エラーは表示されず、単一のものも出力されません。問題がわかりません。なぜこれは印刷されないのですか？ありがとう。

素因数分解関数を書いたのですが、いじってみると、いくつかの数値に問題があることに気づきました...

私のコードの何が問題になっていますか？

erlangにeratosphenesのふるいを実装しようとしています。ただし、アルゴリズムの2番目のステップを通過できません。マークされたエントリにpを入力して、pより大きい値が見つかるまでリストを調べたときに、それも素数であることがわかるようにします。

++で追加しようとしましたが、同じ結果になります。

これは、後の段階で数の除算をチェックする素数を見つけるための簡単なプログラムです。

複雑さを分解するために、最初に数値の整数平方根をとることで、それを短縮しようとしました。それでも、スクリプトの実行には非常に時間がかかります。実行時間を短縮するためにコードに実装できるその他の変更 (既に最大実行時間を 5 分に設定しています)

EDIT sqrt の行にコメントを付けたのは、これが正しいように思われるためです..しかし、それでもループには多くの時間がかかります。

http://projecteuler.netから問題 3 を解決しようとしています。ただし、プログラムを実行しても何も出力されません。私は何を間違っていますか？問題: 数 600851475143 の最大の素因数は?

したがって、素因数分解と除数取得のためのアルゴリズム (ネットで簡単に検索可能) がありますが、範囲内でそれらの除数を見つけるためにそれをスケーリングする方法がわかりません。たとえば、23 から 49 (任意) までの 100 のすべての約数。しかし、効率的なものでもあるので、これをより大きな範囲で大きな数にスケーリングできます。最初は、範囲のサイズである配列を使用してから、すべての素数 <= 上限を使用して、その配列内のすべての要素をふるいにかけて、除数の最終的なリストを返すことを考えていましたが、大きな範囲の場合、これもそうですメモリ集約的。

除数を直接生成する簡単な方法はありますか?