c++ - 是否值得记住质数测试？

Question

我还有另一个回溯挑战，其中我必须得到所有可能的素数组合，这些组合加起来是一个特定的数字。我已经使用Wikipedia中的通用算法完成了任务，但是对于数字 100，运行了一个多小时，到下课时还没有完成。我想知道：记忆化（你怎么拼写？）会显着提高算法的性能（比如，它会不会让它明显更快）？我正在使用 c++，并且该函数被调用了很多次。我正在使用递归回溯，我似乎记得对于简单的问题大约是 O(n!)。

Answer 1

在函数外部创建一个数组，检查主要性和可访问性。全局或静态，取决于使用的语言。该数组将包含所有找到的主要数字。

If the number in question is in the array, return true. 
if number is less or equal than squared max number in the array, return false.
Check for divisibility for all known primaries
if the number is primary, write it into array and return true
return false

添加很简单。这样做并检查更改的时间。