初稿时间:04-18
定稿时间:
推敲过程请点击

质数判定

对于一个给定的正整数N，如何判定其为质数(合数)？

• 2到Root(N)区间，不存在任何一个整数能整除N，则N为质数(更容易理解:在这个区间，只要存在一个整数能整除N，则N为合数)
  伪代码(以下Root(N) 表示N的平方根):

Def  is_Prime(N):
    flag=0 
    For num from  2  to   Root(N):
        IF    num能整除N
            flag=1
            break
   IF   flag=0
         print   N为质数
   Else
        print   N为合数

总结一下存在任何一个 就成立 与 不存在任何一个才成立的代码思路:

flag = 0
for 循环
      if   conditionTrue
             flag = 1
             break
if     flag = 0
     print   不存在任何一个元素符合循环条件
else 
     print    只要有一个元素符合循环条件

考虑到时间复杂度，可做如下优化:

• 3到Root(N)区间，没有任何一个奇数能整除N(这个区间的偶数不可能成为质数的因数)，则N为质数:

Def     is_Prime(N):
    flag=0
    For num  from 2 to  Root(N),   step=2  :
            IF    num能整除N
                    flag=1
                    break
    IF   flag=0
          print  N为质数
    Else
           print    N为合数

接下来用python3实现优化后的伪代码

文件保存为 prime.py

#!/usr/bin/env python3

import sys,os
import math

''''
实现
- 判断整数N是否为质数
- 打印整数N范围内所有的质数
- 计算整数N范围内所有质数的个数

'''

def prime_flag(n):
    """
    如果flag的值为0，则n为质数
    如果flag的值为1，则n为合数

    """

    flag = 0
    num = int(math.sqrt(n))
    for i  in range(2, num+1):
        if  int(n) % i == 0:
            flag = 1
            break
    return flag

def is_prime(n):
    flag = prime_flag(n)
    if flag == 0:
        print(str(n) + " is a prime number")
    else:
        print(str(n)+" is a composite numbe")

def print_all_prime(integer):
    prime_list = [2,]
    prime_count = 1


    for  n  in  range(3, integer + 1 , 2):
        flag = prime_flag(n)
        if  flag == 0:
            prime_list.append(n)
            prime_count += 1

    print("整数N范围内的质数:\n" , prime_list)
    print("这些质数的总数为: %d " %  prime_count)


if __name__ == "__main__":
    print("本程序有以下功能:\n1 判断您输入的整数是否为质数\n
2列出您输入的整数的范围内所有的质数\n
3 计算这些质数的数量\n")
    n = int(input("请输入一个大于3的整数>>>"))
    is_prime(n)
    print_all_prime(n)

2018年4月21日在centos7 python3测试成功