为什么机器学习无法识别素数？

Question

编辑：我将其移至cstheory.stackexchange.com

我想对整数的输入序列进行二进制决策。对于序列中给定的n，输出是否为质数。不要使用AKS，不要使用Miller Rabin，不要使用试验除法，甚至不要硬编码，因为最后一位必须为1,3,7,9，并且必须与1或5一致模6。

仅使用机器学习。

我不确定，但我认为“一般共识”是/将是机器学习技术（神经网络，SVM，二进制分类器，聚类，贝叶斯推理等）将无法解决这个问题？

人们怎么看？

好的，其次，如果我们有一些带有一些有用信息的整数的矢量表示（未知），该原理在机器学习方面能够将n归类为质数或复合数有什么主要的反对意见，只要我们可以“选择正确的功能”这么说？

让我们忽略平凡的情况，其中向量包含n的因式分解。

Answer 1

机器学习并不是一切的答案。机器学习，顾名思义，是从数据中学习。问题是，为了学习一些东西，我们需要数据中的一种模式，我们可以教算法学习。

\n\n

根据定义：素数是大于 1 的自然数，除了 1 和它本身之外没有正因数。

\n\n

这里的基本困难是素数序列

\n\n

2、3、5、7、11、13、17、19、23、. 。。

\n\n

行为 \xe2\x80\x9cunpredictively\xe2\x80\x9d 或 \xe2\x80\x9crandomly\xe2\x80\x9d，我们没有第 n 个素数的（有用的）精确公式！

\n\n

即使您尝试训练算法，您也会得到近似解决方案的东西。\n你无法选择足够好的特征来预测解决方案。

\n\n

比方说，最困难的方法是使用以下功能来训练模型：

\n\n

\n
• 任何以偶数结尾的数字（2 除外）都不是质数。
\n
• 所有数字相加等于 3、6、9 或其约数的任何数字都不是质数。
\n
• 任何以 5 结尾的数字都不是素数。（5个除外）
\n
• 任何数字相同的数字都不是素数。（除非以 1 结尾）
\n

\n\n

您最终会得到所有以 1、3、7 或 9 结尾的素数，但并非所有素数都是素数。

\n\n

因此，当我们想要一个精确的解决方案并且已经有精确的计算方法时，就没有必要找到一种算法来近似某些东西。

\n