判断是否为素数,时间复杂度最低的代码
时间: 2023-08-27 18:03:44 浏览: 53
一个时间复杂度最低的判断素数的方法是使用试除法,代码如下:
```
bool isPrime(int n) {
if (n <= 1) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0 || n % 3 == 0) return false;
int i = 5;
while (i * i <= n) {
if (n % i == 0 || n % (i + 2) == 0) return false;
i += 6;
}
return true;
}
```
这个方法的时间复杂度是 O(√n),比其他方法更优秀。
相关问题
判断素数时间复杂度最低的代码c++
以下是时间复杂度为O(sqrt(n))的C代码,用于判断一个数是否为素数:
```c
#include <stdio.h>
#include <math.h>
int is_prime(int n) {
if (n <= 1) return 0;
if (n == 2) return 1;
if (n % 2 == 0) return 0;
int m = sqrt(n);
for (int i = 3; i <= m; i += 2) {
if (n % i == 0) return 0;
}
return 1;
}
int main() {
int n;
printf("Enter a number: ");
scanf("%d", &n);
if (is_prime(n)) {
printf("%d is a prime number.\n", n);
} else {
printf("%d is not a prime number.\n", n);
}
return 0;
}
```
这里的is_prime函数使用了O(sqrt(n))的算法,因为如果一个数n不是素数,那么它一定可以分解成两个因数a和b,其中a和b中至少有一个小于等于sqrt(n)。所以只需要在2到sqrt(n)之间枚举因子,如果找到了一个能够整除n的因子,就说明n不是素数。
c 判断一个数是否为素数 时间复杂度
判断一个数是否为素数的常见方法是使用试除法。我们可以使用一个循环从2开始遍历到该数的平方根,并检查是否能整除该数。如果存在能整除该数的因子,则该数不是素数,否则该数是素数。
以下是一个C语言实现的示例代码:
```c
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
bool IsPrime(int n) {
if (n < 2) {
return false;
}
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
return false;
}
}
return true;
}
```
时间复杂度分析:该方法的时间复杂度为O(sqrt(n)),其中n是给定的数。