Py学习  »  Python

检查该数字是否是python中的质数

Hellwishween • 6 年前 • 1580 次点击  

我一生中第一次从零开始学习编程。我正在学习Python语言。我的第一个困难任务是写Algorythm,它检查数字是否是素数。

脚本应该以非常简单的方式工作。输入:

是主(29)

你应该得到这样的输出:

数字29是质数。

数字29不是质数。

我没有在网上查到任何解决方案。我自己做的。我的假设如下:

  1. 在学校里,我记得素数只除以1本身。
  2. “0”和“1”不是质数

所以我写了一个代码,检查给定的数字是否被从2到(数字-1)的所有数字所除。例如,如果给定值为“6”,脚本将首先检查6是否除以2。如果这是真的,这意味着数字不是质数。如果6不除以2,脚本将检查6是否除以3。如果是这样,这意味着数字不是质数。如果是“7”,脚本将检查7/2、7/3、7/4、7/5、7/6。

代码如下:

def is_prime(number):
    if number == 0 or number == 1:
        print(f"The number {number} is NOT the prime number.")
    elif number == 2:
        print(f"The number {number} is the prime number.")
    else:
        for i in range(2, number):
            if number % i == 0:
                check = "is NOT"
                break
            else:
                check = "is"
        print(f"The number {number} {check} the prime number.")

但后来,我意识到了三件事:

  1. 如果数字除以2,肯定不是质数
  2. 如果数字不除以2,则可以除以3或5。
  3. 如果数字不除以2,不除以3,也不除以5,这意味着这个数字是质数。本规则的唯一例外是这三个数字2、3和5。

就这样。所以我写的代码如下

def is_prime(number):
    if number > 1:
        if (number %2 == 0 and number != 2) or (number %3 == 0 and number != 3 ) or(number %5 == 0 and number != 5):
            print(f"The number {number} is NOT the prime number. ")
        else:
            print(f"The number {number} is the prime number. ")

    else:
        print(f"The number {number} is NOT the prime number. ")

我认为两种解决方案都可以。 如果我错了请纠正我 但我想问你,从编程的角度来看,哪种解决方案更好?

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/39125
 
1580 次点击  
文章 [ 4 ]  |  最新文章 6 年前
pfRodenas
Reply   •   1 楼
pfRodenas    6 年前
def is_prime(number):

    count = 0

    for i in range(1,number+1):

        if number%i == 0:
            count +=1

    if count == 2:

        print('The number {0} is the prime number.'.format(number))

    else:

        print('The number {0} is NOT the prime number.'.format(number))
Hellwishween
Reply   •   2 楼
Hellwishween    6 年前

关于我的第一个解决方案,你确认的另一件事是正确的。 在“for”循环中要检查的范围是:

for i in range(2, number)

但是,如果我错了,请纠正我,我认为这足够有范围=(2,数字/2)

例如,让我们考虑数字541,它是质数。我的代码将按如下方式检查模块:

541/2 541/3 541/4 . . . 541/538年 541/539年 541/540个

但是检查大于270值(几乎是541的一半)的分型是完全无用的。如果541不除以270,很明显它不能除以271、272、273、274、275等等。

所以我认为有以下条件就足够了:

for i in range(2, round(number/2)+1)

我必须添加+1,否则我在运行3号函数时会出错。

你怎么认为? 我说的对吗,它足够有检查范围(2,数字/2)而不是(2,数字)?

Matthieu Brucher
Reply   •   3 楼
Matthieu Brucher    6 年前

您的原始代码看起来正确。第二个不排除 49 .

Tommy Pedersen
Reply   •   4 楼
Tommy Pedersen    6 年前

即使您的第一个是正确的,而第二个是错误的,您也可以通过以下方式在算法中获得速度:

  1. 如果要尝试的数字是可分割的,不要尝试测试 除法已经是前面数字的一个因子,例如 当你试图用2除的时候,你只需要尝试奇数 数字。如果一个数字不能被2整除,它显然不能被2整除。 可被4整除。
  2. 您只需要测试到的平方根 号码。至少有一个因素需要小于或 等于平方根。