python-算素数

昨天因为复习的缘故，只写了78个字，导致日更断了一天，还好有复活卡。不过六天只能用一次。

今天本来都打算放弃了，但是又觉得辛辛苦苦坚持的两个月，就这样断掉有点可惜，所以还是开始写了这篇（23:28）。

素数的概念我就不多说了。

对于素数这个问题，有多种考法：

• 某一个数是不是素数
• 某一个范围内的素数有哪些？
• 。。。。

很多，今天就说下如何判断某一范围内的素数有哪些。

第一种也是实现起来最简单的，但是效率最低的：
从头开始遍历，判断每个数是否是素数，如果是则保存。这里还涉及到判断一个数是否是素数，这里就不说了，总之效率很低。

现在将一个高效率的方法：
利用映射，键值对，键是某一个范围内的所有整数，值是布尔值，True为素数，False为合数。

我们先初始化这个字典，将所有的值都设置为False，然后遍历字典，把所有的奇数设置为True，因为偶数中除了2以外，都不可能是素数，所以我们再单独把2的值设为True，然后在从3开始遍历，将所有是当前遍历值得倍数的值都设置为False，遍历完成后字典中所有值为True的键都是素数。

因为用的字典，是一种哈希结构，速度非常快，不过数量也要在计算机的处理能力范围内。

源代码：

class Empty(Exception):
    pass


class CircularQueue:
    class _Node:
        def __init__(self, element, next):
            self._element = element
            self._next = next

    def __init__(self):
        self._tail = None
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise Empty("Queue is Empty！")
        return self._tail._next._elelment

    def enqueue(self, e):
        newest = self._Node(e, None)
        if self.is_empty():
            newest._next = newest
        else:
            newest._next = self._tail._next
        self._tail = newest
        self._size += 1

    def dequeue(self):
        if self.is_empty():
            raise Empty("Queue is Empty！")
        head = self._tail._next
        answer = head._element
        if self._size == 1:
            self.tail = None
        else:
            self._tail._next = head._next
        self._size -= 1
        return answer

    def rotate(self):
        if self._size > 0:
            self._tail = self._tail._next

设置了3000000，总用时大概10s.
emmmmm
我将结果保存在txt中了：

image.png

我忘记换行了，将就看吧！

好的今天就这样，明天就要迎接三门考试了，加油！