Primes Leetcode шешімдері


Күрделілік дәрежесі оңай
Жиі кіреді Amazon алма Capital One Google Microsoft
Хэш математика

Бұл есепте бізге бүтін N саны беріледі, мақсаты N-ден кіші сандардың жай сан болатындығын санау. Бүтін сан теріс емес деп шектелген.

мысал

7
3
10
4

Түсіндіру

10-нан кіші жай сандар 2, 3, 5 және 7-ге тең, сондықтан санау 4-ке тең.

Тәсіл (қатал күш)

Жалпы тәсіл - бұл N-ден кіші бүтін санды тексеру және егер олар жай болса, нәтижені көбейту. Мысалы, N = 10 қарастырайық. Енді осы диапазонда қанша жай сан болатынын анықтау үшін 2 - N - 1 аралығында тексеру жүргізе аламыз. Бірақ, бұл тәсіл бүкіл ауқымды тексеруді қажет етеді, [2, N - 1].  Сондықтан бұл баяу.

Біз келесідей оңтайландыруларды жасай аламыз:

  1. 2-ден басқа жай нөмірлердің барлығы тақ сан болып табылады. Сонымен, кейін 2, біз тек тақ сандарды тексере аламыз.
  2. Біз санның қарапайым екенін тексере аламыз O (√N) алгоритмді жетілдіру уақыты.

Алайда, бізде осы мақалада кейінірек талқыланған жақсы тәсіл бар.

Алгоритм

  1. Егер саннан аз болса 3, оралу 0, өйткені 2 ең кіші жай
  2. 3-тен бастап барлық сандарды тексеретін циклды іске қосыңыз
  3. Сан, N жай болып табылады, егер:
    • Онда бар негізгі факторлар 2 мен √N
  4. Егер сан жай болса, нәтижені көбейтіңіз
  5. Нәтижені басып шығарыңыз

Count Primes Leetcode шешімдерін енгізу

C ++ бағдарламасы

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int N)
{
    for(int i = 2 ; i * i <= N ; i++)
        if(N % i == 0)
            return false;
    return true;
}


int countPrimes(int N)
{
    if(N < 3)
        return 0;
    int cnt = 1;
    for(int i = 3 ; i < N ; i += 2)
        if(isPrime(i))
            cnt++;

    return cnt;
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

Java бағдарламасы

class count_primes
{
    static boolean isPrime(int N)
    {
        for(int i = 2 ; i * i <= N ; i++)
            if(N % i == 0)
                return false;

        return true;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        int cnt = 1;//since number is atleast 3, 2 is a prime less than N
        for(int i = 3 ; i < N ; i += 2)
            if(isPrime(i))
                cnt++;
        return cnt;
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

Count Primes Leetcode шешімдерінің күрделілігін талдау

Уақыттың күрделілігі

Біз циклды іске қосамыз N / 2 рет. Әрбір тексерісте O (N / 2) күрделілік уақыты (орташа мәнін ескере отырып) N / 2) жұмсалады. Сонымен, бұл алгоритмнің уақыт күрделілігі мынада O (N√N).

Ғарыштың күрделілігі

O (1), Тұрақты айнымалылар үшін тек тұрақты кеңістік қолданылады.

Тәсіл (оңтайлы әдіс)

Айталық, кез-келген жай санды қарастырайық 5, өзінен басқа 5-тің барлық көбейткіштері ешқашан жай бола алмайтындығына сенімді, өйткені олардың негізгі факторларының бірі ретінде 5 болады. Сол сияқты, біз барлық сандарды N-ден кіші және одан үлкен санда сақтай аламыз 0

The Эратостен електері ежелгі және тиімді алгоритм болып табылады, ол кезде N-ден кіші жай бөлшектерді табуға болады N O (N) бөлуге жеткілікті аз жадыдағы кеңістік. Ол жай емес сандардың барлығын құрама ретінде белгілеу арқылы итеративті түрде жояды. Барлық композиттер белгіленгеннен кейін, белгіленбеген сандар жай сан болып табылады.

Сондай-ақ, біз логикалық затты сақтауымыз керек массив жадтың қолданылуын ескеретін қандай-да бір нөмірдің белгіленген-белгіленбегенін тексеру үшін. Сонымен, бұл біз болған жағдай сауда жады өшіру уақытында жақсарту.

Primes Leetcode шешімдері

Алгоритм

  1. Логикалық массивті ұстаңыз Премьер өлшемі тең N - 1
  2. қарапайым [] соңында композиттерді белгілеу және жай бөлшектерді тексеру үшін қолданылады
  3. Әрбір бүтін санның бас әріптері шынайы. Алгоритм жиынтығы жалған жай емес санға
  4. 2-ден бастап, бүтін санның бірінші еселігі болғанға дейін қатарлы бүтін сандар циклін жүргізіңіз N-ден аз:
    • Әрбір бүтін х үшін, егер оның мәні [x] ақиқат болса, оның барлық еселігін былай белгілеңіз жалған
    • Мұндағы барлық санның еселігі басталады x * x өйткені х-тің барлық еселіктері белгіленбейді.
  5. Соңында [2, N - 1] аралығында қанша сан бар екенін тексеріңіз шынайы қарапайым кестеде
  6. Нәтижені басып шығарыңыз

Count Primes Leetcode шешімдерін енгізу

C ++ бағдарламасы

#include <bits/stdc++.h>
using namespace std;

int sieve(int N)
{
    if(N < 3)
        return 0;

    int cnt = 0;
    bool prime[N];
    for(int i = 2 ; i < N ; i++)
        prime[i] = true;

    for(int i = 2 ; i * i < N ; i++)
    {
        if(prime[i])
            for(int j = i * i ; j < N ; j += i)
                prime[j] = false;
    }

    for(int i = 2 ; i < N ; i++)
        if(prime[i])
            cnt++;

    return cnt;
}

int countPrimes(int N)
{
    if(N < 3)
        return 0;
    return sieve(N);
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

Java бағдарламасы

class count_primes
{
    static int sieve(int N)
    {
        if(N < 3)
            return 0;

        int cnt = 0;
        boolean[] prime= new boolean[N];
        for(int i = 2 ; i < N ; i++)
            prime[i] = true;

        for(int i = 2 ; i * i < N ; i++)
        {
            if(prime[i])
                for(int j = i * i ; j < N ; j += i)
                    prime[j] = false;
        }

        for(int i = 2 ; i < N ; i++)
            if(prime[i])
                cnt++;

        return cnt;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        return sieve(N);
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

Count Primes Leetcode шешімдерінің күрделілігін талдау

Уақыттың күрделілігі

Алгоритмнің күрделілігі мынада O (Nlog (logN)). Мұны келесідей дәлелдеуге болады:

Әрбір бүтін Х үшін біз уақытты өткіземіз Жоқ оның барлық еселіктерін жою.

Сонымен, жалпы жұмсалған уақыт: N / 2 + N / 3 + N / 5 + N / 7 + ……

N-ті қарапайым деп қабылдап, T (N) = N (1/2 + 1/3 + 1/5 + 1/7 +…). Серияның қосындысын (1/2 + 1/3 + 1/5 + 1/7 + ...) келесідей дәлелдеуге болады журнал (logN).

Сондықтан, T (N) = Nlog (logN)

Ғарыштың күрделілігі

O (N), егер біз сан жай немесе жоқ болса, сақтау үшін хэш-кесте құрған кезде.