博客
关于我
leetCode 204 计数质数(埃氏筛法)
阅读量:271 次
发布时间:2019-03-01

本文共 536 字,大约阅读时间需要 1 分钟。

题目链接:

题目描述:

给定一个数字
n
,求小于
n
的质数的个数。
 
输入输出:
 
输入:n = 10输出:4
输入:n = 1输出:0

题目分析:

本题用埃氏筛法(素数筛)可以十分简便的解出这道题,其原理为从 1 n 遍历,假设当前遍历到 m,则把所有小于 n 的、且是 m 的倍数的整数标为和数;遍历完成后,没有被标为和数的数字即为质数。

代码:

int countPrimes(int n){	if(n<=2)	return 0;	vector
prime(n,true); int count=n-2;//去掉不是质数的1 for(int i=2;i<=n;++i) { if(prime[i]) for(int j=2*i;j

优化: 利用素数的一些特性可以对代码进行优化

int countPrimes(int n){	if(n<=2)	return 0;	vector
prime(n,true); int i=3,sqrtn=sqrt(n),count=n/2;//偶数一定不是质数 while(i<=sqrtn)//最小质因子一定小于等于开方数 { for(int j=i*i;j

 

转载地址:http://oxlx.baihongyu.com/

你可能感兴趣的文章
MySQL8.0.29启动报错Different lower_case_table_names settings for server (‘0‘) and data dictionary (‘1‘)
查看>>
MYSQL8.0以上忘记root密码
查看>>
Mysql8.0以上重置初始密码的方法
查看>>
mysql8.0新特性-自增变量的持久化
查看>>
Mysql8.0注意url变更写法
查看>>
Mysql8.0的特性
查看>>
MySQL8修改密码报错ERROR 1819 (HY000): Your password does not satisfy the current policy requirements
查看>>
MySQL8修改密码的方法
查看>>
Mysql8在Centos上安装后忘记root密码如何重新设置
查看>>
Mysql8在Windows上离线安装时忘记root密码
查看>>
MySQL8找不到my.ini配置文件以及报sql_mode=only_full_group_by解决方案
查看>>
mysql8的安装与卸载
查看>>
MySQL8,体验不一样的安装方式!
查看>>
MySQL: Host '127.0.0.1' is not allowed to connect to this MySQL server
查看>>
Mysql: 对换(替换)两条记录的同一个字段值
查看>>
mysql:Can‘t connect to local MySQL server through socket ‘/var/run/mysqld/mysqld.sock‘解决方法
查看>>
MYSQL:基础——3N范式的表结构设计
查看>>
MYSQL:基础——触发器
查看>>
Mysql:连接报错“closing inbound before receiving peer‘s close_notify”
查看>>
mysqlbinlog报错unknown variable ‘default-character-set=utf8mb4‘
查看>>