1

这些问题似乎主要有两部分：首先，弄清楚如何解决问题，采取哪些步骤，需要哪些功能，哪些变量，计数器等，其次，优化该系统以能够处理巨大的数字。

似乎如果我只是有一个更快的功能来查找素数，我将能够将它插入我当前的“解决方案”并返回并回答我不得不跳过的可能二十个或更多的问题，因为它需要我的“解决方案”得到答案的时间不合理（但它会得到答案）。事实上，我试图从头开始想出一切（这样我确信我理解它是如何工作的），而且我确信我的公式不是最理想的。

第二个，优化部分，是整个挑战吗？我还应该骄傲吗？查找一些选择素数和分解函数然后将它们复制粘贴到我当前太慢的解决方案中会不会是作弊？

4

1 回答 1

3

只有当你认为这是作弊时，它才是作弊。我不。事实上，我开始研究素数和整数分解的方式与您现在所做的完全一样。

顺便说一句，这里有一个简单的函数来查找小于n的素数；该算法是 2000 多年前由 Cyrene 的 Eratosthenes 发明的：

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 回答