Python计算素数个数的两种方法
作者：机器学习Zero 发布时间：2023-09-09 16:38:19
标签：Python,素数
素数（prime number）也叫质数，为大于1的且除1和本身以外不再有其他因数的自然数，与之相对的是合数，素数有无限个。
计算小于N的素数个数
输入: 10
输出: 4
小于10的素数共4个：2, 3, 5, 7
方法一：直接判断
from math import sqrt
def isPrime(n):
for i in range(2,int(sqrt(n))+1):
if n％i==0:
return False
return True
def countPrime(N):
if N<3:
return 0
else:
cou = 1
for i in range(3,N,2):
if isPrime(i):
cou += 1
return cou
print(countPrime(2))
print(countPrime(5))
print(countPrime(100))
print(countPrime(100000))
print(countPrime(10000000))#在n>100000000时达到计算瓶颈
输出：
0
2
25
9592
664579
方法二：埃氏筛法
埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法，是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.～194B.C.)提出的一种筛选法。
要得到自然数n以内的全部素数，必须把不大于n的所有素数的倍数剔除，剩下的就是素数，具体步骤如下：先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个质数，也就是3筛，把3留下，把3的倍数剔除掉；接下去用下一个质数5筛，把5留下，把5的倍数剔除掉；不断重复下去。
def couPrime(N):
primeList = [True]*N
for i in range(2,N):
if(primeList[i]):
for j in range(2*i,N,i):
primeList[j]=False
cou = primeList.count(True)-2
return cou
print(couPrime(100000000)) #在n>1000000000达到计算瓶颈
输出：
5761455
来源：https://viper.blog.csdn.net/article/details/128961329
0
投稿猜你喜欢
一、同一台电脑需要安装2个MYSQL，以mysql-5.7.39和mysql-8.0.30为例； 1.下载：https://dow- fckconfig.js 中修改 添加 FCKConfig.LineHeights = '100％;150％;200％;250％;3
- 学习目标根据原型设计编译自动化数据生成器，熟悉wxPython的基本用法。界面原型设计界面原型设计分析输入参数：最大长度最小长度组成规则多少
- 用python编表白程序的方法：1、创建GUI窗口，实现代码的调用。2、编写点击触发函数，实现表白程序。具体代码如下：from tkinte
- 这里假设你是通过models的ImageField上传图片，并期望在前台img标签中能显示。能否访问图片关键在于，是否能通过正确的路径访问。
- 这篇文章主要介绍了Python timer定时器两种常用方法解析,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值
- 本文介绍一下 Pytorch 中常用乘法的 TensorRT 实现。pytorch 用于训练，TensorRT 用于推理是很多 AI 应用开
- 大家好，我是J哥。在我们的工作中，面临着大量的重复性工作，通过人工方式处理往往耗时耗力易出错。而Python在自动化办公方面具有极大的优势，
- 函数：strip() lstrip() rstrip()作用：去除字符串中的空格或指定字符一、默认用法：去除空格st
- 五、XML带来的好处 （1）更有意义的搜索 数据可被XML唯一的标识。没有XML，搜索软件必须了解每个数据库是如何构建的。这实际上是不可能的
- 如下所示：import sysfrom PyQt5.QtWidgets import *class MainWindow(QMainWind
- 一、连接MYSQL：格式： mysql -h主机地址 -u用户名 -p用户密码1、例1：连接到本机上的MYSQL。首先在打开DOS窗口，然后
- 关于Tensor的数据类型说明1. 32位浮点型：torch.FloatTensora=torch.Tensor( [[2,3],[4,8]
- 1。在Asp页面首部<head>加入 Response.Buffer =
- 一、模拟数据库数据1-1 创建数据库及表脚本 - vim slap.sh#!/bin/bash HOSTNA
- 1.前言：将测试数据全部敲入数据库非常繁琐，而且如果与合作伙伴一起开发，部署，那么他们肯定也不想把时间花在一个一个录入数据的繁琐过程中，这时
- 发现问题写python的时候出现了这个错，然后网上的教程的解决方案几乎都是——“重新定义下这个变量”，看的我一脸懵逼后来发现原来是我把ret
- MySQL数据库没有增量备份的机制，但它提供了一种主从备份的机制，就是把主数据库的所有的数据同时写到备份数据库中。实现MySQL数据库的热备
- 前提准备：1.使用python requests模块2.了解json3.zabbix api的具体调用建议先浏览一下官网先上代码：impor
- python图像爬虫包 最近在做一些图像分类的任务时，为了扩充我们的数据集，需要在搜索引擎下爬取额外的图片来扩充我们的训练集。搞人工智能真的
