擅长:python、mysql、java
<p>重新编写代码,将少于100万的素数计算在内,速度提高3倍:</p>
<pre><code>class Solution(object):
def countPrimes(self, n):
primelist = []
for i in range(2, n):
if self.primeCheck(i, primelist):
primelist.append(i)
return len(primelist)
def primeCheck(self, n, primes):
if n < 2:
return False
if n % 2 == 0: # 2 is the only even prime
return n == 2
for prime in primes:
if prime * prime > n: # easier to square many than sqroot one
return True
if n % prime == 0: # divisible by a prime, not a prime
return False
return True
solution = Solution()
print(solution.countPrimes(1000000))
</code></pre>
<p>这包括@rossum向你指出的一些技巧。在</p>
<p>但是,我们可以做得更好。下面是一个使用<a href="https://stackoverflow.com/a/45445010/5771269">@ClockSlave's prime sieve code</a>的重新实现,当计算小于100万的素数时,它比原来快了22倍:</p>
^{2}$
<p>这里的胜利是消除所有这些昂贵的分歧。在</p>