平方时间复杂度：o（n2），算法的执行时间与输入规模的平方成正比。
指数时间复杂度：o（2^n），算法的执行时间随输入规模呈指数级增长。
更高阶复杂度如o（n!）（ps：多项式复杂度）和o（n^n）（ps：指数复杂度）等。
而空间复杂度是描述算法执行所需的额外空间或内存量。
类似于时间复杂度，它也用大o符号表示，表示算法所需的额外空间随着输入规模增长的界。
理解计算复杂度的重要性在于能够评估和比较不同算法之间的效率，以选择最适合解决问题的算法。
通常情况下，我们希望选择时间复杂度低且空间复杂度较小的算法，以实现更高效的计算和资源利用。
计算复杂度还可以指导算法设计和优化，以提高算法的性能和效率。
而从计算复杂度的角度来说，试除法是一种简单但相对较慢的素数验证方法。
因为试除法需要逐个检查每个可能的除数，当待检查数非常大时，该过程变得非常耗时。
试除法的时间复杂度随待检查数的大小呈指数增长，亦即其时间复杂度是指数级的。
通过试除法来验证素数，不要说是对付千万位的数，就算是对付一些大数，试除法也只会很乏力。
对于大规模的素数，实际应用中是不适用应用试除法验证如此大的数是否为素数。
实际应用中，对于大规模的数，如果要验证其是不是素数一般都采用别的更高效的方式。
至少该方式所对应的复杂度也不能是指数复杂度。
指数复杂度通常意味着问题的解决时间会随着问题规模的增长呈指数级增长。
这并不一定意味着问题无解，而是指在实际计算，对于较大规模的问题，找到解决方案所需的计算资源和时间可能是不可行的。
对于某些问题，尽管其具有指数复杂度，但仍然存在有效的解决方案。
例如，某些组合优化问题，如旅行商问题（Tsp），在理论是指数难解的，但有许多启式算法和近似算法可以在实践中找到接近最优解的解决方案。
然而，对于某些问题，指数复杂度可能意味着找到精确解决方案是困难的或不切实际的。
例如，对于某些特定的组合优化问题，如子集和问题（subsetsum），由于其指数复杂度，当问题规模较大时，无法通过穷举搜索所有可能的解决方案来找到最优解。
因此，指数复杂度并不直接表示问题无解，而是指在实际情况下，对于大规模问题找到精确解决方案可能非常困难。
而如果要验证一个大数是素数除了试除法之外，还有很多别的方式。
譬如说证明一个大数是素数的方法可以使用mi11er-Rabin素数测试。
mi11er-Rabin素数测试是一种概率性测试，可以高概率确定一个数是否为素数。
以下是使用mi11er-Rabin素数测试证明一个大数是素数的一般步骤：
选择一个适当的测试次数（通常是几十到几百次），记为k。
将待检查的大数减1，得到数n-1。
将n-1分解为d*2^s的形式，其中d是奇数，s是非负整数。即n-1=d*（2^s）。
对于每个测试次数，选择一个随机整数a，满足1an-1
计算a^dmodn，并检查结果是否为1或n-1。
如果结果是1或n-1，则进行下一次测试。
如果结果不是1且不是n-1，则进行s-1次迭代计算：计算（a^d）^2modn，依次重复。
如果在k次测试中的任何一次迭代中得到的结果不是1且不是n-1，则n不是素数。
如果在k次测试中所有迭代中都得到的结果都是1或n-1，则n很可能是素数。
需要注意的是，由于mi11er-Rabin素数测试是概率性的，有一定的错误概率。
但是，通过增加测试次数k，可以将错误概率降低到非常小的程度。
这个过程听起来要比试除法繁琐很多。
但从计算复杂度的角度来出，mi11er-Rabin素数测试的时间复杂度是多项式复杂度。
具体而言，它的时间复杂度为o（k*1og?（n）*（1og?（n））3），其中k是测试次数，n是待检查的大数。
在mi11er-Rabin素数测试中，迭代次数是由测试次数k决定的。
每次迭代的计算包括取模运算和幂运算，它们的复杂度都是多项式级别的。
与指数复杂度的算法相比，多项式复杂度的算法在处理大数时更加高效。
尽管mi11er-Rabin素数测试是一种概率性测试，但随着测试次数的增加，错误概率可以降低到极小的程度。
虽然mi11er-Rabin素数测试具有多项式时间复杂度，但如果是对于比大数还要大的数（也就是是说对于一些动辄千万位的数非常大的数），想要验证其是不是素数仍然需要相当大的计算资源和时间才能完成测试。
甚至于在实际应用中，常常会结合其他优化技术和算法来提高素数测试的效率。
而如何验证一个数是不是梅森素数呢？