# [python] good algorithm but Time Limit Exceeded at 1500000

• ``````class Solution(object):
def countPrimes(self, n):
"""
:type n: int
:rtype: int
"""
if n <= 2: return 0
if n == 3: return 1
# l is a list of discovered prime nums
# prime nums other than 2 are all odd
l = [3]

# only test odd nums
for i in range(3, n, 2):
# i is prime if it doesn't have prime factors upto sqrt(i)
# only test prime nums in l as factors
bound = int(i ** 0.5)
for j in l:
if i % j == 0:
break
if j > bound:
l.append(i)
break

# 2 is not in list l, so add it on
return len(l) + 1
``````

I keep a list l to store discovered prime nums and test new number only on those in l and smaller than sqrt(i). I also explicitly skip even numbers larger than 2. This should be a better algorithm than that in hint, better than n ** 1.5. But it end up with Time Limit Exceeded. Any suggestions? Thanks.

• Er, you could use c++/java rather than python. Then you'll got an AC.

I think the limit of runtime in Leetcode are 2000ms no mather which language you use. That means, with the same algorithm, python needs much much more time than c++/java/c/c#. So, you'll got a TLE in python while an AC in c++.

``````// c++ version
class Solution {
public:
int countPrimes(int n) {
if (n <= 2)
return 0;
if (n == 3)
return 1;

vector<int> l;
l.push_back(3);

for (int i = 3; i < n; i += 2) {
int bound = int(pow(i, 0.5));
for (int j = 0; j < l.size(); j++) {
if (i % l[j] == 0)
break;
if (l[j] > bound) {
l.push_back(i);
break;
}
}
}
return l.size() + 1;
}
};``````

• Thanks for your answer. I submitted with your code, which only beat 6% cpp codes. Since my algorithm is better (in terms of space) than one in the hint, there should be other reason I could not tell.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.