Time Limit Exceeded?when n=1500000


  • 0
    J

    public class Solution
    {
    public int CountPrimes(int n)
    {
    bool isP=false;
    int count=0;
    if (n >3)
    {
    count = 3;
    for (int i = 3; i < n; i=i+2)
    {
    isP = isPri(i);
    if (isP == true)
    count++;
    }

            }
            else if(n<=3&&n>0)
            {
                count=n;
            }
            
            return count;
        }
    
        public bool isPri(int i)
        {
            if (i <= 3)
            {
                return true;
            }
            else
            {
                for (int j = 2; j < Math.Sqrt(i); j++)
                {
                    if (i % j == 0)
                    {
                        return false;
                    }
                }
                return true;
            }
    
        }
    }

  • 0
    L

    You'll get TLE (time limit exceeded) error if you call isPri for each number for a large N.
    You need to implement this instead: https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes


  • 0
    J

    thx,this question is solved,However, thank you,this reson that my method is wrong.


  • 0
    X

    I have met the same problem! Could you tell me how did you solve it?


Log in to reply
 

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