OpenMP入门学习笔记-质数筛选
质数筛选 质数的定义：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。 因此对于每个数 x，我们可以从小到大枚举 [2, x−1] 中的每个数 y，判断 y 是否为 x 的因数。这样判断一个数是否为质数的时间复杂度最差情况下会到 O(n)。整体的时间复杂度为O(n^2)。 void naive_prime_sieve(int n, std::vector
质数筛选 质数的定义：在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。 因此对于每个数 x，我们可以从小到大枚举 [2, x−1] 中的每个数 y，判断 y 是否为 x 的因数。这样判断一个数是否为质数的时间复杂度最差情况下会到 O(n)。整体的时间复杂度为O(n^2)。 void naive_prime_sieve(int n, std::vector