Leetcode — Броене на прости числа (средно ниво)

Постановка на проблема: Дадено е цяло число n, върнете броя прости числа, които са строго по-малки от n.

Нека разберем постановката на проблема – да предположим, че ни е дадено n = 10, трябва да върнем броя на просто число в диапазона от 0 до 10. Това означава, че числата са 2,3,5,7, брой = 4

Псст — преди да продължим по-нататък, спомняме си кои прости числа са верни?

Сега да се заемем с решаването на това !!!

Обяснение:

Ще използваме „ Ситото на Ератозен ”( знам, фантастичен термин хехе) . Това е древен алгоритъм (да! и ефективен също) за намиране на прости числа до даден диапазон.

Да кажем, че имаме n = 25. Изброяваме всички числа от 2 до 25.

1. Знаем, че 2 е просто число. В списъка пресечете всички кратни на 2, т.е. 4,6,8,..,24.
2. Преминете към следващото немаркирано число —3 (просто число). В списъка пресечете всички кратни на 3, т.е. 6,9,12..,24.
3. Сега преминете към нашето следващо немаркирано число 5 (просто число)и маркирайте всички кратни на 5, т.е. 10,15,20,25.
4. Повторете за всички немаркирани числа.

Всички останали числа са прости. Ето!

Да започнем кодирането!!

class Solution {
    public int countPrimes(int n) 
    {
      // BASE CASE - Runtime Error otherwise !! 
        if (n==0 || n==1)
            return 0;
        
       int[] primes = new int[n]; 
        Arrays.fill(primes, 0); 
        int count=0; 
        
        primes[0]=1; 
        primes[1]=1; 
        
        for ( int i =2 ; i<n ; i++)
        {
            if(primes[i]==0)
                count++;
            
            for (int j=i+i ; j<n; j+=i)
            {
                primes[j]=1; 
            }
        }
        return count; 
    }
}

Времева сложност: O (n* log (log n ) ) ) — цикълът трябва само да премине през числата до корен квадратен от n и да маркира кратните на всяко просто число.

Пространствена сложност: O(n) — Масив с размер n + 1 се използва за съхраняване на списъка с прости числа.