Primes Leetcode шийдлийг тоолох


Хэцүү байдлын түвшин Easy
Байнга асуудаг Амазоны Apple-ийн Капитал Нэг Google-ийн Microsoft-
Хаширч байна Математик

Энэ бодлогод бидэнд N бүхэл тоо өгөгдсөн бөгөөд N-ээс бага тоо хэрхэн анхдагч болохыг тоолохыг зорилоо. Бүхэл тоо сөрөг биш байхаар хязгаарлагддаг.

Жишээ нь

7
3
10
4

Тайлбар

10-аас бага анхан шатны тоо нь 2, 3, 5 ба 7 байна. Тиймээс тоолол нь 4 байна.

Хандлага (Brute Force)

Ерөнхий хандлага нь N-ээс бага бүхэл тоо бүрийг шалгаж, үр дүнг анхдагч бол өсгөх явдал юм. Жишээлбэл, N = 10-ийг авч үзье. Одоо 2-оос N-1 хүртэлх чекийг ажиллуулж энэ хязгаарт хэдэн үндсэн тоо байгааг олж мэдье. Гэхдээ энэ арга нь бүх хүрээг нарийвчлан шалгахыг шаарддаг. [2, N - 1].  Тиймээс энэ нь удаан байна.

Бид дараахь байдлаар оновчлол хийж болно.

  1. 2-оос бусад анхны тоо бүр сондгой бүхэл тоо байна. Тиймээс, дараа нь 2, бид зөвхөн сондгой бүхэл тоонуудыг шалгаж болно.
  2. Дугаар анхдагч байгаа эсэхийг бид шалгаж болно O (√N) алгоритмыг сайжруулах цаг хугацаа.

Гэсэн хэдий ч бид энэ нийтлэлийн сүүлд хэлэлцсэн илүү сайн арга барилтай хэвээр байна.

Алгоритм

  1. Хэрэв тоо нь түүнээс бага бол 3, буцах 0, 2 бол хамгийн жижиг анхны тоо юм
  2. 3-аас эхлэн бүх дугаарыг шалгах гогцоо ажиллуулна уу
  3. Хэрэв N тоо нь дараахь тоог илэрхийлнэ:
    • Энэ нь 2 ба XNUMX хоорондох үндсэн хүчин зүйлүүд
  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) -ийг хуваарилахад хангалттай хэмжээтэй санах ой дахь зай. Энэ нь бүх энгийн бус тоонуудыг нийлмэл гэж тэмдэглээд давталтаар арилгадаг. Бүх найрлагыг тэмдэглэсний дараа тэмдэглэгээгүй тоонууд нь үндсэн тоо болно.

Түүнчлэн, бид boolean хадгалах хэрэгтэй массив санах ойн ашиглалтыг тооцдог дугаарыг тэмдэглэсэн эсвэл тэмдэглээгүй эсэхийг шалгах. Тиймээс, энэ бол бидний хэрэг худалдааны санах ой унтраах цаг хугацаанд нь сайжруулах.

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 / 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)

Сансрын нарийн төвөгтэй байдал

O (N), тоо нь анхдагч эсвэл үгүй ​​бол хадгалах хэш хүснэгт үүсгэдэг тул.