matlab判断整除函数_判断素数函数
描述
写⼀个函数isPrime(n)⽤于判断⼀个数字n是不是素数，⽤户输⼊⼀个正整数，在⼀⾏内输出不⼤于该数的所有素数，各数后⾯⽤⼀个空格
分隔。
输⼊格式
输⼊⼀个正整数
输出格式
不⼤于该数的所有素数，各数后⾯⽤⼀个空格分隔。
输⼊输出⽰例
输⼊输出
⽰例 1100  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
解析：
素数的概念⼜称为质数，⼀个⼤于1的⾃然数，除了1和它⾃⾝外，不能被其他⾃然数整除的数。
可以定义⼀个函数，传⼊⼀个整数，返回其是否为素数。判定⼀个数是否为素数的⽅法是，⽤传⼊的整数 n 除从2到n-1之间的每⼀个整
数，如果存在某个可以整除的数，则其不是素数，如果没有任何除1和其本⾝以外的因⼦，则其是素数。(时间复杂度为o(n))
# 将判断⼀个整数 n 是否为素数的代码定义为⼀个函数isPrime(n)# 传⼊参数为整数 n，n 是素数时返回值为True，否则返回False# 时间复杂度为o(n)def isPrime(n):
其主程序部分可以修改为以下模式，使当前⽂件可以做为模块被其他程序调⽤。当⽂件直接被运⾏时，if __name__ == "__main__"：语c++判断素数
句后的语句块中的输⼊输出等语句会被执⾏。当⽂件被当做模块import时，只调⽤其中的函数，if __name__ == "__main__"：后的语句块
不会被执⾏。
# 将判断⼀个整数 n 是否为素数的代码定义为⼀个函数isPrime(n)# 传⼊参数为整数 n，n 是素数时返回值为True，否则返回False# 时间复杂度为o(n)def isPrime(n):
我们知道⼀个数若可以进⾏因数分解，那么分解时得到的两个数⼀定是⼀个⼩于等于sqrt(n)，⼀个⼤于等于sqrt(n)，所以对于每个数
n，并不需要从2判断到n-1，遍历到sqrt(n)即可。因为若sqrt(n)左侧不到约数，那么右侧也⼀定不到约数。这样可以显著提升算法的
效率，上⾯判断素数函数可以修改为：
# 传⼊参数为整数 n，n 是素数时返回值为True，否则返回False# 时间复杂度为o(n)def isPrime(n):  # 判断参数 n 是否为素数的函数    if n <= 1:  # ⼩于2的数字都不是
依据经验，我们知道素数分布的规律，除了2以外的所有素数都是奇数，所以可以只判定奇数是否是素数就可以，可以减少⼀半的判定素
数的计算量。
if __name__ == "__main__":    m = int(input())      # 输⼊⼀个正整数    if m > 2:        print(2,end = ' ')    f
or num in range(3,m,2): # 获得⼩于m的整数数列        if isPr    素数分布的规律：⼤于等于5的素数⼀定和6的倍数相邻。例如5和7，11和13,17和19等等。
查看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
可以发现除2和3外，其他数都是6的倍数的相邻数：
6-1，6+1，2*6-1，2*6+1，3*6-1，3*
但要注意，6 的倍数的相邻数并不全是素数，例如35。所以还是需要调⽤素数判定函数进⾏判定。只判定6的倍数的相邻数是否是素数
就可以到所有素数。这样可以进⼀步减少判定的次数，提⾼效率。注意2和3要单独判定。
if __name__ == "__main__":    m = int(input())      # 输⼊⼀个正整数    if m > 2:        print(2,end = ' ')    if m > 3:        print(3,end = ' ')    for num in range(0,m,6):  #
综合以上分析，可以同时优先判定素数的函数和判定的代码：
def isPrime(n):
# 判断参数 n 是否为素数的函数
if n <= 1:      # ⼩于2的数字都不是素数
return False
for i in range(2,int(n ** 0.5) + 1):  # 两因⼦相同时，为保证取到右边界，需加1
# for i in range(2,int(math.sqrt(n)) + 1)
if n % i == 0:    # 从 2到n-1中如果存在⼀个数是i，使n 可以整除i，则n不是素数
return False
else:                  # 若for循环未遇到return正常结束，则n是素数
return True
if __name__ == "__main__":
m = int(input())      # 输⼊⼀个正整数
if m > 2:
print(2,end = ' ')
if m > 3:
print(3,end = ' ')
for num in range(0,m,6):  # 获得⼩于m的整数数列
if isPrime(num - 1):  # 如果isPrime(num -1)返回值为True,num 是素数
print(num - 1,end = ' ')    # 输出num - 1
if isPrime(num + 1):  # 如果isPrime(num + 1)返回值为True,num 是素数
print(num + 1,end = ' ')    # 输出num + 1
除了这些⽅法以外，还可以使⽤筛选法，先⽣成⼩于n的所有数字，再把 2 到 sqrt(n) 之间的整数的倍数依次去掉，剩余的就是⼩于n的
所有素数了。这种⽅法的效率更⾼