专栏名称: 算法与数据结构
算法与数据结构知识、资源分享
今天看啥  ›  专栏  ›  算法与数据结构

如何用算法高效寻找素数?

算法与数据结构  · 公众号  · 算法  · 2019-10-14 09:10
来自公众号:labuladong预计阅读时间:5 分钟素数的定义很简单,如果一个数如果只能被 1 和它本身整除,那么这个数就是素数。不要觉得素数的定义简单,恐怕没多少人真的能把素数相关的算法写得高效。本文就主要聊这样一个函数:// 返回区间 [2, n) 中有几个素数 int countPrimes(int n)// 比如 countPrimes(10) 返回 4// 因为 2,3,5,7 是素数你会如何写这个函数?当然可以这样写:int countPrimes(int n) {    int count = 0;    for (int i = 2; i         if (isPrim(i)) count++;    return count;}// 判断整数 n 是否是素数boolean isPrime(int n) {    for (int i = 2; i         if (n % i == 0)            // 有其他整除因子            return false;    return true;}这 ………………………………

原文地址:访问原文地址
快照地址: 访问文章快照