如何使用MySQL对整数进行因式分解

Question

在我的项目中，我需要使用MySQL找到整数的质因数分解，我认为这是查询除了递归之外的高效方式。我想要实现的是找到组成一个整数的质数。例如：对于102，其质因数将是：17，3，2。谢谢。

- Sundesz Kumar Hyoju

---

分解一个数字是一个非常困难的问题；它是许多加密算法安全性的基础。为什么你需要这样做，以及为什么你需要在MySQL中这样做？ - Philip Kendall

我认为这样做会比进行所有递归操作节省执行时间。 - Sundesz Kumar Hyoju

如果你想快速分解任何小于 10^6 的数字，并且愿意用空间换时间，我建议建立一个简单的查找表格，以 integer 为索引，包含 (整数，因子)。由于只有一百万行，查找应该非常快。当然，填充表中的“因子”是另外一个问题... - eggyal

你可以编写一个存储过程，但为什么要让你的数据库解决这样一个计算量大的问题呢？数据库是用来存储数据的。 - Kos

但是，在支持数组和原始数字类型的编程语言中，将1到10^6（甚至10^8）的数字分解因数也非常快速。筛选最小质因数，然后可以递归地查找其他数字。 - Daniel Fischer

Answer 1

信封背面策略（仍需要编程循环进行第二步）

1. 创建一个名为“primes”的表，只有一个int列（主键）

2. 运行以下循环：

   for $x = 2 to $n {
     execute("
       insert into primes (id) 
       select $x where not exists 
        (select * from primes as p where p.id <= sqrt($x) AND ($x mod p.id) > 0)")
   }
   

3. 使用上述子查询列出特定$x的结果

这个解决方案适用于小于等于$n^2$的值。第二步可以通过仅测试以1、3、7、9结尾的数字中大于9的数字来改进。

- ErichBSchulz