python 素数(筛选法)(简单素数筛选法) | 您所在的位置:网站首页 › python写判断素数函数 › python 素数(筛选法)(简单素数筛选法) |
素数又是质数,以下都按素数表达 筛选法又称筛法,具体做法是: 先把N个自然数按次序排列起来。 1不是质数,也不是合数,要划去。(合数指自然数中除了能被1和本身整除外,还能被其他数(0除外)整除的数。与素数相反) 第二个数2是质数留下来,而把2后面所有能被2整除的数都划去。 2后面第一个没划去的数是3,把3留下,再把3后面所有能被3整除的数都划去。 3后面第一个没划去的数是5,把5留下,再把5后面所有能被5整除的数都划去。 这样一直做下去,就会把不超过N的全部合数都筛掉,留下的就是不超过N的全部质数。 因为希腊人是把数写在涂腊的板上,每要划去一个数,就在上面记以小点,寻求质数的工作完毕后,这许多小点就像一个筛子,所以就把埃拉托斯特尼的方法叫做“埃拉托斯特尼筛”,简称“筛法”。 (另一种解释是当时的数写在纸草上,每要划去一个数,就把这个数挖去,寻求质数的工作完毕后,这许多小洞就像一个筛子。) 步骤分析: 1.输入一个数为N 2.使用for循环遍历2到N 3.设每个i都为素数 即a = 1 4.若i能被2到i-1的整数整除,则i不为素数 即a = 0 5.若a = 1依然成立,则对应i的值为素数 6.输出所有当a = 1时,i的值 # 用简单素数筛选法求N以内的素数。 N = int(input("请输入一个大于2的整数:")) for i in range(2,N): a = 1 #设每个数都为素数 for j in range(2,i): if (i % j ) == 0: #进行筛选 a = 0 #能被整除的都不是素数 if a == 1: print(i) #输出素数运行结果: 请输入一个大于2的整数:100 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 |
CopyRight 2018-2019 实验室设备网 版权所有 |