python求质数的方法有哪些

求质数的方法有以下几种：

1.试除法：从2开始，依次除以小于该数的所有整数，如果都无法整除，则该数为质数。该方法的时间复杂度为O(n)。

2.埃氏筛法：首先创建一个长度为n+1的布尔数组，将所有元素初始化为True。然后从2开始，将所有2的倍数标记为False，然后继续下一个未被标记为False的数，以此类推，直到n的平方根。最后剩下的未被标记为False的数即为质数。该方法的时间复杂度为O(n log(log n))。

3.改进的埃氏筛法：与上述方法类似，但只需要标记奇数的倍数，可以将数组的大小减半。该方法的时间复杂度也为O(n log(log n))。

4.米勒-拉宾素性测试：该方法不是直接判断一个数是否为质数，而是通过判断一个数是否是合数的概率来确定是否为质数。该方法的时间复杂度为O(k log^3 n)，其中k为测试的次数。

5.费马素性测试：与米勒-拉宾素性测试类似，也是通过判断一个数是否是合数的概率来确定是否为质数。该方法的时间复杂度为O(k log^3 n)，其中k为测试的次数。

6.拉宾-米勒素性测试：与米勒-拉宾素性测试类似，也是通过判断一个数是否是合数的概率来确定是否为质数。该方法的时间复杂度为O(k log^3 n)，其中k为测试的次数。

这些方法各有优缺点，选择合适的方法取决于具体情况和需求。