Count Primes Leetcode Solutions


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են 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 լուծումների բարդության վերլուծություն

Timeամանակի բարդություն

Մենք գործարկում ենք օղակ N / 2 ժամանակներ Յուրաքանչյուր ստուգման ժամանակ O (N / 2) բարդության ժամանակ (հաշվի առնելով միջինը որպես N / 2) ծախսվում է: Այսպիսով, այս ալգորիթմի ժամանակի բարդությունը կազմում է O (N√N):

Տիեզերական բարդություն

Ո (1), Անընդհատ փոփոխականների համար օգտագործվում է միայն հաստատուն տարածություն:

Մոտեցում (օպտիմալ մեթոդ)

Հաշվի առեք ցանկացած պարզ թիվ, ասենք 5, ապա համոզված է, որ 5-ի բոլոր բազմապատիկները, բացի ինքն իրենից, երբեք չեն կարող պարզունակ լինել, քանի որ նրանք կունենային 5-ը ՝ որպես իրենց հիմնական գործոններից մեկը: Նմանապես, մենք կարող ենք պահել բոլոր թվերը N- ից պակաս և ավելի մեծ 0

The Երատոսթենեսի մաղը հնագույն և արդյունավետ ալգորիթմ է N- ից պակաս պարզ թվեր գտնելու համար N- ը բավական փոքր է O (N) հատկացնելու համար տարածություն հիշողության մեջ: Այն կրկնօրինակում է վերացնում բոլոր ոչ պարզ թվերը ՝ նշելով դրանք որպես կոմպոզիտային: Բոլոր կոմպոզիտորների նշումից հետո անթվանշված թվերը պարզ թվեր են:

Բացի այդ, մենք պետք է բուլյան պահենք դասավորություն ստուգելու համար, արդյոք որևէ թիվ նշված է, թե ոչ, որը հաշվի է առնում հիշողության օգտագործումը: Այսպիսով, սա այն դեպքն է, երբ մենք առևտրային հիշողություն անջատել դեպի ժամանակին կատարելագործվել.

Count Primes Leetcode Solutions

Ալգորիթմ

  1. Պահպանեք բուլյան զանգված վարչապետ չափի հավասար է N - 1
  2. պարզ [] օգտագործվում է կոմպոզիտորները նշելու և վերջերը պարզելու համար
  3. Յուրաքանչյուր ամբողջ թվերի սկզբնատառ, ինչպես ճիշտ, Ալգորիթմը սահմանում է սուտ յուրաքանչյուր ոչ պարզ թվին
  4. Գործարկեք անընդմեջ ամբողջ թվերի մի օղակ ՝ սկսած 2-ից մինչև ամբողջ ամբողջի առաջին բազմապատիկը պակաս, քան N:
    • Յուրաքանչյուր ամբողջ x թվերի համար, եթե այն պարզ [x] - ն ունի ճշմարիտ, դրա բոլոր բազմապատկերը նշիր որպես սուտ
    • Յուրաքանչյուր ամբողջ թվերի բազմապատիկը այստեղից է սկսվում 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 լուծումների բարդության վերլուծություն

Timeամանակի բարդություն

Ալգորիթմի բարդությունն այն է O (Nlog (logN)): Դա կարելի է ապացուցել որպես.

Յուրաքանչյուր ամբողջ X- ի համար մենք ժամանակ ենք ծախսում N / X վերացնելով իր բոլոր բազմապատիկները:

Այսպիսով, ընդհանուր առմամբ ծախսված ժամանակը `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)

Տիեզերական բարդություն

ՎՐԱ), քանի որ մենք հաշի սեղան ենք ստեղծում ՝ պահելու համար, եթե համարը պարզ է, թե ոչ: