第21章 P/NP问题的本质(1 / 3)
如何证明一个数是素数?
对于这个问题,即便是一个中学生也能很轻松的找到问题的答案。
素数是指大于1的自然数,除了1和它本身之外,没有其他正因数的数。
换句话说,素数只能被1和它自身整除,不能被其他自然数整除。素数的特点是只有两个正因数:1和本身。
而从素数的定义出发的话,就可以通过试除法来验证。
具体来说可以执行下面的操作:
步骤1:选择一个大于1且小于待检查数平方根的数作为除数。如果待检查数为n,则可以选择2到√n之间的数作为除数。
步骤2:将待检查数除以选定的除数。如果除法的余数为,即待检查数能被选定的除数整除,则待检查数不是素数。
步骤3:如果待检查数不能被选定的除数整除,继续增加除数的值,重复步骤2。
步骤4:如果在2到√n之间没有找到能整除待检查数的除数,则待检查数是素数。
不可否认,试除法简单粗暴,但这仅仅限于所要你所要验证的数并不大的时候。
但当问题变成如何证明一个超大的数(这个数有上千万位是素数的时候,再继续用试除法就显得很呆。
这里面主要涉及到计算复杂度的问题。
(计算复杂度听起来是一个计算机方面的问题。
但正如前面说得那样,现代数学和计算机科学之间的关系早已就是你中有我,我中有你。
就算是搞数学的,但凡是涉及到利用计算机作为工具来解决问题的时候就不得不考虑周全。
甚至于很多经典的数学问题其本质上也是计算机问题。
就比如说七个数学千禧难题之一的p/np问题就既是数学问题,同时也是计算机问题。
更具体来说,其本质是计算复杂度的问题。
p指的是可多项式时间内解决的问题,而np是指可多项式时间内验证解的问题。
p/np问题是计算复杂度理论中的重要问题。它们涉及了算法是否存在有效的解决方法以及在何种时间内可以解决问题的核心问题。