Count primes ---ACM 题目

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5901
AC代码: http://www.cnblogs.com/TAT1122/p/5883884.html
很不理解是什么原理.求大牛讲讲是根据什么来解出的这道题.谢谢 本问题是ACM题目.

1个回答

举个例子吧:比如算100以内的质数个数,
首先,列出100开平方,也就是10以内的所有质数
2,3,5,7
然后
N0 = 100
N1 = 1+N0-N0/2 = 1+100-100/2 = 51 (去除2的倍数后的个数)
N2 = 1+N1-N1/3 = 1+51-51/3 = 1+51-17=35 (去除3的倍数后的个数)
N3 = 1+N2-N2/5 = 1+35-35/5 = 1+35-7 = 29 (去除5的倍数后的个数)
N4 = 1+N3-N3/7 = 1+29-29/7 = 1+29-4 = 26 (去除7的倍数后的个数)
个数 K=N4-1=25, (剩下的数字中,1不是质数)
答案: 25个
自己多想想就好了

WR_technology
Code--Dream 请问你是想用容斥定理?
大约 3 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
HDU 5901 Count primes【数论】
Count primes Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 903    Accepted Submission(s): 481 Problem Description Easy question!
leetcode笔记:Count Primes
题目有很多tips,大意是算出2~n之间有多少个素数。 思路来自著名的埃拉托斯特尼筛法。
LeetCode 204:Count Primes
Description: Count the number of prime numbers less than a non-negative number, n 分析: 题目要求计算小于N的所有素数的个数。所有主程序很简单:判断是否是素数字,如是,count++ (暂且忽略prim_vec, 后面判断素数时会用到): int countPrimes(int n) {
LeetCode 204 - Count Primes
一、问题描述Description:Description:Count the number of prime numbers less than a non-negative number, nHint: The number n could be in the order of 100,000 to 5,000,000.二、解题报告解法一首先,我试图在遍历的过程中保存之前所有的质数,然后对于对于
204. Count Primes [easy] (Python)
题目链接https://leetcode.com/problems/count-primes/题目原文 Count the number of prime numbers less than a non-negative number, n. 题目翻译计算小于非负数 n 的所有素数的个数。思路方法想要验证小于n的所有数分别是不是素数,如果暴力的判断每个数是否能整除所有小于它的数,亲测会超时,所以
leetcode 204: Count Primes
Description: Count the number of prime numbers less than a non-negative number, n [思路] 素数不能被比它小的整数整除, 建一个boolean 数组, 从2开始, 把其倍数小于N的都删掉. 注意 inner loop从i开始, 比i小的会在以前就被check过. [CODE] pu
(LeetCode)Count Primes --- 统计素数(质数)
(LeetCode)Count Primes --- 统计素数(质数)
POJ 3978 Primes(求范围素数个数)
POJ 3978 Primes(求范围素数个数) http://poj.org/problem?id=3978 题意: 给你一个区间范围A和B,要你求出[A,B]内的素数个数。其中B<=100000。 分析: 首先我们求出2到10W的素数表,把每个素数按从小到大的顺序保存在prime数组中。然后我们用二分查找找到A的下界和B的上界,然后用上界-下界即为素数个数。 程序实现用了两种筛选法来求素数表。两种筛选法都是基于每个自然合数都可以分解为:最小素因子p*剩余部分q。
Python 刷题日记:LeetCode 204: Count Primes
原题: Description:Count the number of prime numbers less than a non-negative number, n.解题思路:常规解法:因为要求解小于n的素数个数,首先要解决如何判断一个素数。那么就是对于一个数x,只需对[2,]的数进行整除,若能整除则不是素数,不能整除则为素数。然后判断小于n的各个数是否为素数,这样做法的复杂度显然为O(n^2
[LeetCode 204] Count Primes(Python)
题目描述 Count the number of prime numbers less than a non-negative number, n. 思路开辟一个辅助数组,依次标记2−n√2-\sqrt n的所有倍数。最后遍历该数组,计数素数。代码class Solution(object): def countPrimes(self, n): """ :
HDU 5901 Count primes 2016年沈阳网络赛 (Lehmer素数计数)
Count primes Time Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 155    Accepted Submission(s): 28 Problem Description Easy question! Calcul
【LeetCode-面试算法经典-Java实现】【204-Count Primes(统计质数)】
【204-Count Primes(统计质数)】【LeetCode-面试算法经典-Java实现】【所有题目目录索引】代码下载【https://github.com/Wang-Jun-Chao】原题  Description:   Count the number of prime numbers less than a non-negative number, n. 题目大意  统计小于非负整数
[LeetCode-204] Count Primes(0~n 有多少个质数—4种方法求解)
埃拉托色尼筛选法 (1)先把1删除(现今数学界1既不是质数也不是合数) (2)读取队列中当前最小的数2,然后把2的倍数删去 (3)读取队列中当前最小的数3,然后把3的倍数删去 (4)读取队列中当前最小的数5,然后把5的倍数删去 (5)如上所述直到需求的范围内所有的数均删除或读取
HDU 5901 Count Primes (模板 + 数论知识)——2016 ACM/ICPC Asia Regional Shenyang Online
传送门 Count primesTime Limit: 12000/6000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 635    Accepted Submission(s): 299Problem Description Easy question! Calculate
LeetCode 204 Count Primes(质数计数)(*)
翻译计算小于一个非负整数n的质数的个数。原文Count the number of prime numbers less than a non-negative number, n.分析这道题以前遇到过,当时是用的最笨的办法,现在也没什么好想法,又恰好题目有提示,我就点开了。题目的提示是一条一条给出来的,我也就逐个的全点开了,感觉好失败……public int countPrimes(int n)
hdu 5901 Count primes
题意输出[1..n]的质数个数 (1 <= n <= 1e11) 。时间限制6s,空间限制64M 。题解很显然,要用线性筛的话时间和空间都不够。有一种Meissel–Lehmer算法可以解决该问题,不过本文要介绍的是一种dp解法。定义SR(n,p)SR(n,p)为,2..n2..n被小于等于pp的质数筛后剩下的数的个数;也就是说,在n的范围内,是质数,或者是只由大于pp的质数相乘得到的数的个数。
LeetCode--Count Primes(素数个数)Python
题目: 计算n以内的素数个数。 解题思路: 1、首先考虑直接判断n以内的每个数是否为素数。再对结果进行求和。判断某个数是否为素数的方法,之间判断该数能否整除从2到sqrt(n)的数字。若能则是素数,否则不是素数。复杂度为n*sqrt(n)。但在LeetCode会超时。 代码(Python): class Solution(object): def countPrimes(self
【LeetCode】(204)Count Primes(Easy)
题目 Count Primes  Total Accepted: 27781 Total Submissions: 139375My Submissions Question  Solution  Description: Count the number of prime numbers less than a non-negative
HashTable-204-Count Primes
Description: Count the number of prime numbers less than a non-negative number, n. Solution: class Solution { public int countPrimes(int n) { boolean[]isPrime = new boolean[n]; ...
沈阳网赛1010 HDU 5901 Count primes
求前n个数中质数的个数。这里要用到Meisell-Lehmer的n^(2/3)的方法,借用了一大牛的板子。 //Meisell-Lehmer #include #include using namespace std; #define LL long long const int N = 5e6 + 2; bool np[N]; int prime[N], pi[N]; int getp
hdu5901 Count primes
hdu5901两种方法我也不会,留个纪念。 http://blog.csdn.net/define_danmu_primer/article/details/52588027
LeetCode中Count Primes的java实现
题目如下: Description: Count the number of prime numbers less than a non-negative number, n. 一开始用的方法入下,结果运算时间太大 public class Solution {     public int countPrimes(int n) {        boolean mar
关于一些初级ACM竞赛题目的分析和题解(三)。
关于一些初级ACM竞赛题目的分析和题解(三)。 今天,辣鸡monster_ayb终于自己做出一道A题算是一点点小进步吧,今天的两道题算是很好理解的,主要是辣鸡ayb以前吧,是知道题目的思路,却不会写,现在练的多了有一点点小的进步,废话少说,直接上题:                                                           266A    A. S
HDU 5901 Count primes (求1e11内素数个数)
死亡之题…… 比赛打表打了3小时,想的是分段打表一些边界数据,类似这题:把1e9分成5000个20W大小的区间,打表出区间边界(1,200000,400000...)的答案。这样最坏查找最多也是20W-1 结局是三小时也没打出来,在第四小时的时候发现就算表打出来复杂度也在1e11左右,亲妈爆炸! 最最后的结局是,论文题:Wiki 或者 Lehmer快速求1e11以内质数个数
LeetCode编程练习 - Count Primes学习心得
题目:         Count the number of prime numbers less than a non-negative number,n.         给定一个非负数n,求小于n的质数的个数。 思路:         定义一个变量,初始值为0,用来装载质数,再定义一个变量遍历所有数,因为第一个质数是2,因此,初始值设为2,用布尔值来判断是否是质数,若是质数
HDU 5901 Count primes(求1e11内素数个数模板)
板子: #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; using namespace std; const int N = 5e6 + 2; bool np[N]; int prime[N], pi
(大组合数)D. Fence Building ------ ACM-ICPC 2017 Asia Urumqi
传送门: D.Fence Building Farmer John owns a farm. He first builds a circle fence. Then, he will choose n points and build some straight fences connecting them. Next, he will feed a cow in each region ...
ACM中好用的SET
Set 集合 百度百科中的对集合特性的描述 集合中的元素有三个特征:1.确定性(集合中的元素必须是确定的) 2.互异性(集合中的元素互不相同。例如:集合A={1,a},则a不能等于1) 3.无序性(集合中的元素没有先后之分。) STL中封装的set保证了元素的确定性,互异性(没用重复元素),而且神奇的是STL中的set中的元素是有序的! 在STL中,卓越的前辈们在c++里为我们封装好了
leetcode 204 Count Primes(计算质数) python3 多种思路(动态素数表/埃氏筛法/)
class Solution: def countPrimes(self, n): &amp;amp;quot;&amp;amp;quot;&amp;amp;quot; :type n: int :rtype: int &amp;amp;quot;&amp;amp;quot;&amp;amp;quot; # 思路一: 简单的遍历除以小于他的数,效率太低了! # 思路二: 遍历除以小于他一半的数,有率提升
2018ACM-ICPC中国大学生程序设计竞赛线上赛I. Reversion Count(数论&规律)
题目链接:https://nanti.jisuanke.com/t/26217 26.87% 1000ms 65536KDescription:There is a positive integer X, X's reversion count is Y. For example, X=123, Y=321; X=1234, Y=4321. Z=(X-Y)/9, Judge if Z is mad...
Count Primes
Description: Count the number of prime numbers less than a non-negative number, n class Solution { public: int countPrimes(int n) { if (n < 2) { return 0; }
ACM竞赛题目简介ACM竞赛题目简介
ACM竞赛题目简介ACM竞赛题目简介ACM竞赛题目简介ACM竞赛题目简介
ACM基础与入门 许多acm题目解题答案
acm是大学生程序竞赛中最常见的,对于一个程序员而言,参加acm不仅能够拓宽自己的知识面,而且能够在参加比赛的同时,认识一些新的朋友,而这些朋友可能在以后的生活中,对你产生很大的影响,对于一个非专业的程序员来说,如果能够参加acm竞赛,那么不仅能够培养自己的兴趣爱好,而且更能巩固知识面!
count primes
Count Primes Description: Count the number of prime numbers less than a non-negative number, n 1. 给定一个数n,初始化一个长度比n稍微大一点的数组,num[n+1],将其初始化为1. 2. (判断m是否是素数的标准是是否存在{2, ..., sqrt(m)}
Count primes
一般的解法: 1,构建一个isPrime函数,对每一个n检测,从2扫到n-1,看是否有整除的。每个判断的时间复杂度就是O(n),整体时间复杂度O(n^2); 2,其实扫到n/2就可以判断; 3,其实扫到i*i 4,可是如果n很大,这些方法都不好。因为终究要对每个n判断是否为质数。如果采用排除法,直接将已知的质数的倍数剔除。如果每个质数的从2开始的倍数进行剔除,很不划算,因为有很多重复的。
第八届ACM趣味程序设计竞赛第三场(正式赛)官方题解
UESTC 第八届ACM趣味程序设计竞赛第三场(正式赛)题解 若有疑问建议先看题解然后自己代码实现,实在不行再看文章最后的标程 A - 渐变字符串 B - 保护果实 C - Little_Pro的driver朋友们和他的魔法 D - 扑克斗争 E - shallowdream and girl
ACM各题型OJ题目总结
本帖题目类型: 1)递归与分治 2)动态规划 3)贪心算法 4)回溯算法 5)图的搜索算法 6)图论 7)数论 8)组合数学 9)分支限界算法 推荐网站:https://vjudge.net/ 下面给出各题型的部分例题。 注:1.题目来源于ZOJ,POJ和HUD;         2.同一个题目可采用多种解法,本帖题目分类不代表最优解法。
杭电ACM题目类型整理
版权声明:(╯3╰) 转载请注明: http://blog.csdn.net/bat67 杭电acm题目分类版本1 1002 简单的大数 1003 DP经典问题,最大连续子段和 1004 简单题 1005 找规律(循环点) 1006 感觉有点BT的题,我到现在还没过 1007 经典问题,最近点对问题,用分治 1008 简单题 1009 贪
ACM试题 实例分析 含很多题目
ACM试题 ACM题目分析 ACM试题 ACM题目分析
ACM各类题目集
大佬博客:qscqesze                  16级电子科技大学大佬                  16级北大大佬的博客 ---&amp;gt;大佬  Cf题目选讲:https://wenku.baidu.com/view/348f684c33687e21af45a9c9.html?from=search 2011年世界冠军,浙江大学巫泽俊(watashi)大神的blog 【其...
相关热词 c# oracle 开发 c#选择字体大小的控件 c# usb 批量传输 c#10进制转8进制 c#转base64 c# 科学计算 c#下拉列表获取串口 c# 如何防止参数被修改 c#开发微信公众号例子 c# null