204. 计数质数 (素数筛法)

2024-02-17 11:38
文章标签 计数 质数 素数 204 筛法

本文主要是介绍204. 计数质数 (素数筛法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description

统计所有小于非负整数 n 的质数的数量。

示例 1:输入:n = 10
输出:4
解释:小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
示例 2:输入:n = 0
输出:0
示例 3:输入:n = 1
输出:0来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/count-primes
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
Solution 素数筛法
class Solution:def countPrimes(self, n: int) -> int:if n==0: return 0primes = [1]*(n+1)primes[0] = primes[1] = 0for i in range(n+1):if primes[i]:for j in range(i+i, n+1, i):primes[j] = 0res = 0for i in range(n):if primes[i]: res += 1return res

这篇关于204. 计数质数 (素数筛法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/717639

相关文章

YOLOv8/v10+DeepSORT多目标车辆跟踪(车辆检测/跟踪/车辆计数/测速/禁停区域/绘制进出线/绘制禁停区域/车道车辆统计)

01:YOLOv8 + DeepSort 车辆跟踪 该项目利用YOLOv8作为目标检测模型,DeepSort用于多目标跟踪。YOLOv8负责从视频帧中检测出车辆的位置,而DeepSort则负责关联这些检测结果,从而实现车辆的持续跟踪。这种组合使得系统能够在视频流中准确地识别并跟随特定车辆。 02:YOLOv8 + DeepSort 车辆跟踪 + 任意绘制进出线 在此基础上增加了用户

归并排序/计数排序

1:归并排序 1.1:代码 void _MergeSort(int* arr, int left, int right, int* tmp){if (left >= right){return;}int mid = (left + right) / 2; _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid+1, righ

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比

【CF】C. Glass Carving(二分 + 树状数组 + 优先队列 + 数组计数)

这题简直蛋疼死。。。。。 A了一下午 #include<cstdio>#include<queue>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int maxn = 200005;int h,w,n;int C1[maxn],C2[maxn];int

js算法题,给任意一个偶数,找出他的所有的质数因子

/*给任意一个偶数,找出他的所有的质数因子*/ function primeFactor(n){     var factors=[],            divistor=2;     if(typeof n !=='number'||!Number.isInteger(n)){          return 0;     }; //如果不是偶数返回0,如果是0,返回0

js算法判断是否为素数

/*判断一个数字是否是质数: 质数(prime number)又称素数,有无限个。除了1和它本身以外不再被其他的除数整除。*/ function isPrime(number){ //判断输入是否为number类型,是否为整数       if (typeof number!=='number'||!Number.isInteger(number))      {

【时时三省】c语言例题----华为机试题< 查找组成一个偶数最接近的两个素数>

山不在高,有仙则名。水不在深,有龙则灵。                                                                         ----CSDN 时时三省 1,题目 HJ60 查找组成一个偶数最接近的两个素数 描述 任意一个偶数(大于2)都可以由2个素数组成,组成偶数的2个素数有很多种情况,本题目要求输出组成指定偶数的两个

题目:求100以内的素数,全部打印出来。

题目:求100以内的素数,全部打印出来。 public class ZhaoSuShu {public static void isPrime1(){int i,j,count = 0;//System.out.println("2");for(i = 1; i <= 100; i++){for(j = 2; j <= i; j++){if(i % j == 0){break;}}if(j ==

素数判定和分解质素数

1.素数判定   public static boolean isPrime(int n) {if (n <= 1) return false;if (n == 2) return true;if (n % 2 == 0) return false;int limit = (int)Math.sqrt(n) + 1;for (int i = 3; i <= limit; i += 2) {i

Java-计算素数

判断输入的数字是不是素数: public class SuShu{public static void main(String[] args){java.util.Scanner s=new java.util.Scanner(System.in);int i=s.nextInt();boolean isSuShu=true; //标记;for(int j=2;j<i;j++){if(i%j=