网络编程
位置：首页>> 网络编程>> Python编程>> python求质数的3种方法

python求质数的3种方法

作者：z大酱　　发布时间：2023-02-12 04:07:54　

标签：python,质数

本文为大家分享了多种方法求质数python实现代码，供大家参考，具体内容如下

题目要求是求所有小于n的质数的个数。

求质数方法1：

穷举法：
根据定义循环判断该数除以比他小的每个自然数（大于1），如果有能被他整除的就不是质数：


def countPrimes1(self, n):
 """
 :type n: int
 :rtype: int
 """
 if n<=2:
  return 0
 else:
  res=[]
 for i in range(2,n):
  flag=0 # 质数标志，=0表示质数
  for j in range(2,i):
   if i％j ==0:
    flag=1
  if flag==0:
   res.append(i)
 return len(res)

求质数方法2：

利用定理：如果一个数是合数，那么它的最小质因数肯定小于等于它的平方根。所以判断一个数是否是质数，只需判断它是否能被小于它开根后的所有数整除。这样做的运算会少很多。


def countPrimes2(self, n):
 if n<=2:
  return 0
 else:
  res=[]
 for i in range(2, n):
  flag=0
  for j in range(2, int(math.sqrt(i))+1):
   if i ％ j == 0:
    flag = 1
  if flag == 0:
   res.append(i)
 return len(res)

求质数方法3：

利用定理：如果一个数是合数，那么它的最小质因数肯定小于等于它的平方根。我们可以发现只要尝试小于等于平方根的所有数即可。列举从 3 到根号x的所有数，还是有些浪费。比如要判断101是否质数，101的根号取整后是10，需要尝试的数是1到10。但是可以发现，对9的尝试是多余的。不能被3整除，必然不能被9整除……顺着这个思路走下去，其实，只要尝试小于根号x的质数即可。而这些质数，恰好前面已经算出来了，已经存在res中了。


def countPrimes3(self, n):
 if n <= 2:
  return 0
 else:
  res = []
 for i in range(2, n):
  flag = 0
  for j in res:
   if i ％ j == 0:
    flag = 1
  if flag == 0:
   res.append(i)
 return len(res)

来源：https://blog.csdn.net/zhangwei15hh/article/details/78471593

0
投稿

猜你喜欢

  • 随滚动条移动的DIV层js代码，无论你的滚动条到哪里这个DIV层就跟到哪里！代码中例举了五个方向的滚动div层例子：包括左上方的div，左下
  • 学习WEB标准的朋友一般都是从学习CSS开始，为什么呢？因为CSS是一种很有意思的语言，它能让我们的网页千变万化。也许我们一开始的接触只是因
  • 合并多张图片到视频的方法说明除了使用 OpenCV 合并多张图片成视频外，还可以使用其他工具和库，例如：moviepy: 这是一个基于 Py
  • 阅读上一篇：FrontPage XP设计教程3——网页的布局 FrontPage XP可以保证用户设计网页与不同的浏览器兼容，它所提供的样式
  • 什么是浮动？浮动是 css 的定位属性。我们可以看一下印刷设计来了解它的起源和作用。印刷布局中，文本可以按照需要围绕图片。一般把这种方式称为
  • 如下所示：#coding utf-8a=0.001    #定义收敛步长xd=1    #定义寻找步
  • 创建视图创建视图success.blade.php<!doctype html><html lang="{{ s
  • ASP有一个最重要的功能，就是它可以让你非常轻松地连接数据库。通常都是和一个Access或者一个SQL数据库相连。因为Access是最容易起
  • 前言：由于公司使用钉钉，之前告警都是使用邮箱，但是这种协同效率比较低，所以调用钉钉机器人来实现实时告警。创建机器人：创建钉钉群，然后添加群机
  • 1、从数据库表中检索信息实际上，前面我们已经用到了SELECT语句，它用来从数据库表中检索信息。select语句格式一般为：SELECT 检
  • 这些CSS Selector在平时写页面的时候用地不多，只在JavaScript库、Firefox插件、iPhone页面里有过接触。推荐大家
  • 当我们使用传统的 mysql_connect 、mysql_query方法来连接查询数据库时，如果过滤不严，就有SQL注入风险，导致网站被攻
  • 一个正则表达式就是由普通字符（例如字符 a 到 z）以及特殊字符（称为元字符）组成的文字模式。该模式描述在查找文字主体时待匹配的一个或多个字
  • 本文实例讲述了php中正则替换函数ereg_replace用法。分享给大家供大家参考。具体如下：下面的实例是利用php 正则替换函数 ere
  • 先说说线程在多线程中，为了保证共享资源的正确性，我们常常会用到线程同步技术.将一些敏感操作变成原子操作，保证同一时刻多个线程中只有一个线程在
  • 用扩展名判断文件格式非常简单，但是有可能是错误的。 jpeg文件有固定的文件头，其文件头的格式如下：Start Marker | JFIF
  • 关于mysql数据库在Linux下的应用一直以来都是我认为比较棘手的，这次通过搭建Linux学习环境顺便研究和学习Mysql数据库在Linu
  • 功能是：以一个关键字为索引，搜索整个数据库，然后返回那个关键字所在的表名和列名。（很赞...特别是入侵的时候找不到用户名与密码所在的表的时候
  • PHP crc32() 函数实例输出 crc32() 的结果：<?php $str = crc32("Hello World
  • 先从String的扩展开始吧，后面有一部分的扩展要依赖这里扩展的方法。为了更加清晰和详细，我会一个方法一个方法地贴出来，你完全可以把所有的方
手机版 网络编程 asp之家 www.aspxhome.com