编辑 : 我将这个问题移至 cstheory.stackexchange.com

我希望对一个整数序列进行二元决策。对于序列中的给定 n，输出它是否为素数。不要使用 AKS，不要使用 Miller Rabin，不要使用试除法，甚至不要硬编码最后一位必须是 1,3,7,9 并且必须与 6 同余 1 或 5。

只使用机器学习。

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

大家怎么看？

其次，如果我们有一些携带有用信息的整数向量表示（未知），原则上是否有任何主要反对意见，阻止机器学习能够将 n 分类为素数或合数，假设我们能够“选择正确的特征”？

让我们忽略向量包含 n 的因子分解的简单情况。

回答：

机器学习并不是解决一切问题的答案。正如其名，机器学习是从数据中学习的。问题在于，要学习某事，我们需要数据中的模式来教算法学习。

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

这里的基本难点在于素数序列

2, 3, 5, 7, 11, 13, 17, 19, 23, . . .

表现得“不可预测”或“随机”，我们没有第 n 个素数的（有用）精确公式！

即使你尝试训练一个算法，你得到的也将是近似解。你无法选择足够好的特征来预测解。

假设，你以艰难的方式训练你的模型，使用这些特征：

• 任何以偶数结尾的数字（除了 2）都不是素数。
• 任何各位数字之和等于 3, 6, 9 或其因数的数字都不是素数。
• 任何以 5 结尾的数字都不是素数。（除了 5）
• 任何相同数字的数字都不是素数。（除非以 1 结尾）

你最终会发现所有素数都以 1, 3, 7 或 9 结尾，但并非所有以这些数字结尾的数都是素数。

因此，当我们想要一个精确的解法，并且已经有精确的计算方法时，就没有必要寻找一个近似解的算法了。