Count the number of prime numbers less than a non-negative number, n.
Example:
Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.
My code:
class Solution(object):
def countPrimes(self, n):
if n <= 2:
return 0
res = 1
prime = [True] * n
for i in range(3, n, 2):
if prime[i]:
res += 1
j = 3
while i*j < n:
prime[i*j] = False
j += 2
return res
def countPrimes1(self, n):
"""
:type n: int
:rtype: int
"""
if n<=1:
return 0
if n<=2:
return 0
#discard 2 first
count=1
for item in range(3,n,2):
flag=True
for item1 in range(2,int(item/2)+1):
if item%item1==0:
#print('%d removed by %d'%(item,item1))
flag=False
break
if flag:
count+=1
return count
Solution: https://leetcode.com/problems/count-primes/submissions/