Python

Question

在这个素数和算法中：

Let S(v,p) be the sum of integers in the range 2 to v that remain after sieving with all primes smaller or equal than p. That is S(v,p) is the sum of integers up to v that are either prime or the product of primes larger than p.

S(v,p) is equal to S(v,p−1) if p is not prime or v is smaller than p2. Otherwise (p prime, p2≤v)S(v,p) can be computed from S(v,p−1) by finding the sum of integers that are removed while sieving with p. An integer is removed in this step if it is the product of p with another integer that has no divisor smaller than p. This can be expressed as

S(v,p)=S(v,p−1)−p(S(⌊v/p⌋,p−1)−S(p−1,p−1))

def P10(n):
    sqrt = int(n**0.5)
    V = [n//i for i in range(1,sqrt+1)]
    V += list(range(V[-1]-1,0,-1))
    S = {i:i*(i+1)//2-1 for i in V}
    for p in range(2,sqrt+1):
        if S[p] > S[p-1]:  # p is prime
            sp= S[p-1]  # sum of primes smaller than p
            p2 = p*p
            for v in V:
                if v < p2: break
                S[v] -= p*(S[v//p] - sp)

 return S[n]

我对这部分有点困惑：

if S[p] > S[p-1]:  # p is prime

这是否意味着 S 中的值是通过索引 p 访问的？ p 的值范围从 2 到 sqrt，而 S 从 V 得到它的索引。不会导致索引异常吗？？

谢谢。 *我是 python 新手

Answer 1

S 是一个字典，通过键访问，使用类似于列表索引访问的语法。 'key' 区别在于：

如果失败会return KeyError（在这个例子中p不是S中的key）
在 S 中保存了一个特定的值来表示 p - 注意构造函数中的冒号 {i:i*(i+1)//2-1 for i in V}。键设置为 V 中的列表项，链接值设置为其后的数学运算结果。

花括号{}表示正在构造Dictionary，冒号分隔键赋值和赋值。

Python - 素数之和

Python - Sum of primes

primes