求100以内的质数

求100以内的质数

题目说明

输出100以内的所有素数,素数之间以一个空格区分
分析:
首先了解下素数:素数(prime number)又称质数,有无限个。一个大于1的自然数,除了1和它本身外,不能被整除以其他自然数(质数),换句话说就是该数除了1和它本身以外不再有其他的因数;否则称为合数。最小的质数是2。

解决方案

  1. 使用试除法,看看比n小的数中有没有n的因数,如果没有,那么该数就是素数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution:
    def output_all_prime(self):
    """
    :rtype: list
    """
    res = list()
    for i in range(2, 101):
    flag = True
    for j in range(2, i):
    if i % j == 0:
    flag = False
    break
    if flag:
    res.append(i)
  2. 升级版试除法,我们没必要对小于n的所有整数进行试除法,只要试除2到根号n就行了。因为因数都是成对出现的。成对的因数,其中一个必然小于等于根号n,而另一个一定大于根号n。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    import math

    class Solution:
    def output_all_prime(self):
    """
    :rtype: list
    """
    res = list()
    for i in range(2, 101):
    flag = True
    for j in range(2, int(math.sqrt(i)) + 1):
    if i % j == 0:
    flag = False
    break
    if flag:
    res.append(i)
  3. 更pythonic的做法:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    import math
    class Solution:
    def output_all_prime(self):
    """
    :rtype: list
    """
    print(' '.join(['%s' % x for x in range(2, 101) if not [y for y in range(2, int(math.sqrt(x) + 1)) if x % y == 0]]))
    #或者
    print(' '.join([str(i) for x in range(2, 101) if not [y for y in range(2, int(math.sqrt(x) + 1)) if x % y == 0]]))

说明: 如果您有更好的解决方案或者本人写的有什么问题,请多多指教!