1

質問には主に2つの部分があるようです.1つ目は、問題へのアプローチ方法、実​​行する手順、必要な機能、変数、カウンターなどを理解することです。2つ目は、そのシステムを最適化して、巨大な数を扱います。

たとえば、素数を見つけるためのより高速な機能があれば、それを現在の「ソリューション」にプラグインして、戻って、スキップしなければならなかったおそらく20以上の質問に答えることができるようです。私の「解決策」が答えを得るのに不当な時間です（しかし、それは答えを得るでしょう）。現状では、私はゼロからすべてを考え出そうとしました (そうすれば、それがどのように機能するかを理解していると確信しています)。

2 番目の最適化の部分は、課題全体ですか? それでも誇りに思うべきですか？選択した素数と因数分解関数を調べて、それらを現在の遅すぎるソリューションにコピー アンド ペーストするのは不正行為でしょうか?

4

1 に答える 1

3

浮気だと思ったらただの浮気です。私はしません。実際、私は素数と整数因数分解の研究を、あなたが現在行っているのとまったく同じ方法で始めました。

ところで、これはnより小さい素数を見つける単純な関数です。このアルゴリズムは、キレネのエラトステネスによって 2000 年以上前に発明されました。

function primes(n)
    sieve := makeArray(2..n, True)
    for p from 2 to n
        if sieve[p]
            output p
            for i from p*p to n step p
                sieve[i] := False

そして、これは試行分割を使用して数値nの約数を見つける単純な関数です。

function factors(n)
    f := 2
    while f*f <= n
        while n % f == 0
            output f
            n := n / f
        f := f + 1
    if n <> 1 output f

両方の機能を改善する方法があります。素数を使ったプログラミングに興味がある場合は、私のブログでこのエッセイをお勧めします。

于 2013-08-17T11:45:45.190 に答える