试除法判定质数算法总结

知识概览

质数的定义

在大于1的整数中，如果只包含1和本身这两个约数，就被称为质数，或者叫素数。

质数的判定——试除法

暴力算法        时间复杂度

改进算法        时间复杂度 

暴力算法：时间复杂度O(n)

算法模版

bool is_prime(int n)
{if (n < 2) return false;for (int i = 2; i < n; i++)if (n % i == 0)return false;return true;
}

优化算法：时间复杂度O(sqrt(n))

算法模版

bool is_prime(int n)
{if (n < 2) return false;for (int i = 2; i <= n / i; i++)if (n % i == 0)return false;return true;
}

例题展示

题目链接

活动 - AcWing系统讲解常用算法与数据结构，给出相应代码模板，并会布置、讲解相应的基础算法题目。https://www.acwing.com/problem/content/868/

题解

用试除法的改进版本可以解决，否则会超时。

代码

#include <iostream>
#include <algorithm>using namespace std;bool is_prime(int x)
{if (x < 2) return false;for (int i = 2; i <= x / i; i++)if (x % i == 0)return false;return true;
}int main()
{int n;cin >> n;while (n--){int x;cin >> x;if (is_prime(x)) puts("Yes");else puts("No");}return 0;
}

参考资料

1. AcWing算法基础课