当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

判断一个数是质数的几种方法

发表于: 2013-05-17   作者:EmmaZhao   来源:转载   浏览:
摘要: 质数也叫素数,是只能被1和它本身整除的正整数,最小的质数是2,目前发现的最大的质数是p=2^57885161-1【注1】。 判断一个数是质数的最简单的方法如下: def isPrime1(n): for i in range(2, n): if n % i == 0: return False return True 但是在上面的方法中有一些冗余的计算,所以
质数也叫素数,是只能被1和它本身整除的正整数,最小的质数是2,目前发现的最大的质数是p=2^57885161-1【注1】。
判断一个数是质数的最简单的方法如下:
def isPrime1(n):
	for i in range(2, n):
		if n % i == 0:
			return False
	return True

但是在上面的方法中有一些冗余的计算,所以做以下改进
def isPrime2(n):
	import math
	if n == 1:
		return False
	elif n < 4:
		return True
	else:
		r = int(math.floor(math.sqrt(n)))
		for i in range(2,r+1):
			if n % i == 0:
				return False
		return True

上面的方法对第一种方法做了一些改进,但是还可以再细分一些情况,如下:
def isPrime(n):
	import math
	if n == 1:
		return False
	elif n < 4:
		return True
	elif n & 1 == 0:
		return False
	elif n < 9:
		return True
	elif n %3 == 0:
		return False
	else:
		r = math.floor(math.sqrt(n))
		f = 5
		while f <= r:
			if n % f == 0:
				return False
			if n %(f+2) == 0:
				return False
			f += 6
		return True

判断15485863是否是素数时,三者的运行时间如下:
1.9960000515
0.0139999389648
0.0090000629425


4. 打表法:
可以事先列出M(M为正整数)下的素数表,判断一个数是否为素数时,可以直接在表中查找,这是最快的方法了,但是需要额外的存储空间,是一种用空间换取时间的方法。
下面是列出M以下的所有素数的一种方法。
def primeBelowM(m):
	num = [True for i in range(m)]
	for i in range(2,m):
		k = (m-1)/i
		for j in range(2,k+1):
			num[j*i] = False
	prime = []
	for i in range(2,m):
		if num[i]:
			prime.append(i)
	return prime



【注1】
引用
http://baike.baidu.cn/view/333373.htm

判断一个数是质数的几种方法

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
虽说已经找到了实习,offer也拿了,但是还是决定多上来刷刷一些简单的,很水的笔试面试题。 这些题
Copyright (c) 2012, 烟台大学计算机学院 All rights reserved. 作 者: 刘元龙 完成日期:2012 年1
上机内容:练习循环 上机目的:学会编写循环程序 /* *copyright()2012计算机学院 *All rights res
/* * 程序的版权和版本声明部分: * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved
/* *Copyright (c)2013,烟台大学计算机学院 *All rights reserved. *文件名称:test.cpp *作者:孙
/* *Copyright (c)2013,烟台大学计算机学院 *All rights reserved. *文件名称:test.cpp *作者:王
/* * 程序的版权和版本声明部分: * Copyright (c) 2012, 烟台大学计算机学院 * All rights reserved
/* *程序的版权和版本声明部分: *Copyright(c)2013,烟台大学计算机学院学生 *All rights reserv
这是我写的质数判断程序,数数有多少个错误吧…… 都是年轻时候犯下的错啊…… 1 #include<stdio
这是我写的质数判断程序,数数有多少个错误吧…… 都是年轻时候犯下的错啊…… 1 #include<stdio
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号