በክልሎች ውስጥ ፕራይሞችን ይቆጥሩ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ google ረጅም መንገድ ተንሸራሸረ ኩሊዛ ሳኒ Snapchat ያሁ
ሒሳብ የቁጥር ስርዓት

የችግሩ መግለጫ

ችግሩ “በክልሎች ውስጥ ፕራይሞችን ይቆጥሩ” የሚለው ክልል [ግራ ፣ ቀኝ] እንደሚሰጥዎ ይገልጻል ፣ የት 0 <= ግራ <= ቀኝ <= 10000። በችግሩ ውስጥ ያለው የጠቅላላ ቁጥሮች ጠቅላላ ቁጥር ለማወቅ የችግሩ መግለጫ ይጠይቃል። ብዛት ያላቸው መጠይቆች እንደሚኖሩ በማሰብ ፡፡

ለምሳሌ

left: 4
right:10
2

ማስረጃ

5 እና 7 ብቸኛው 2 ዋና ቁጥሮች ናቸው ፡፡

በክልሎች ውስጥ ፕራይሞችን ይቆጥሩ

left: 6
right:8
1

ማስረጃ

7 ብቸኛው ብቸኛው ቁጥር ነው ፡፡

አልጎሪዝም

  1. ፍጠር ኢንቲጀር ድርድር እና የቦሊያን ድርድር 'ፕራይም' በከፍተኛው የተሰጠው መጠን እና የቦሊያን ድርድርን ከ ጋር ይጀምሩ እውነተኛ.
  2. የቦሊያን ድርድርን በማለፍ የ ‹ፕራይም› ድርድር የአሁኑ ዋጋ እውነት ከሆነ ያረጋግጡ ፡፡
  3. ከዚያ አሁን ካለው የድርድር አካል መሻገር ይጀምሩ እና ከእዚያ ጀምሮ እያንዳንዱን የድርድር አካል ከአሁኑ ንጥረ ነገር መጠን ጋር እኩል በሆነ ርቀት ወደ ሐሰት ያስጀምሩ። ይህ ማለት ወደ የአሁኑ ንጥረ ነገር ብዙዎች እንሸጋገራለን ማለት ነው ፡፡
  4. ቅድመ ፕራይም [0] ን እና ፕሪሚየር [1] እስከ 0 ያቀናብሩ።
  5. ከከፍተኛው እስከ ከፍተኛው እሴት ድረስ ከ 2 ይጓዙ ፡፡
  6. እሴቱን በቀዳሚው የቅድመ-ፕራይም ድርድር መረጃ ጠቋሚ ላይ ይቅዱ እና የዋናው ድርድር የአሁኑ ዋጋ ከእውነት ጋር እኩል መሆኑን ያረጋግጡ ፣ ከዚያ የቅድመ-ፕሪሚየር ዋጋን በ 1 ይጨምሩ።
  7. ለእያንዳንዱ ጥያቄ የቅድመ-ፕሪም [ቀኝ] እና የቅድመ-ፕሪም [ግራ -1] ልዩነት ይመልሱ።

ማስረጃ

የቁጥር ክልል እንደ መነሻ ቁጥር እና እንደ ማብቂያ ቁጥር ተሰጥቷል። ስለዚህ በአከባቢው መካከል ባሉ ቁጥሮች ሁሉ የተሞላ ስለሆነ ይህንን ክልል ከግምት ውስጥ ማስገባት። በዚህ ክልል ውስጥ የጠቅላላ ቁጥሮችን ጠቅላላ ቁጥር ለማወቅ ጠይቀናል ፡፡ ለዚህም ማንኛውንም ቁጥር በከፍተኛው ክልል ውስጥ የምንፈታበት ቅድመ ፕራይም ድርድር እንገነባለን ፡፡ ለእኛ የተሰጠው ከፍተኛ መጠን 10000 የሆነ የኢቲጀር ድርድር ያውጅ እና በተመሳሳይ መጠን እኛ እንደ እውነተኛ እሴት የጀመርነውን የቦሊያን ድርድር እናውጃለን ፡፡

አንደኛውን እንደ ዋና ቁጥር ልንቆጥረው ስለማንችል ከእሴቱ ሁለት በክፍል ውስጥ ተጓዙ ፡፡ እያንዳንዱን የቦሌን ፕራይም ድርድር እያንዳንዱ እሴት ከእውነተኛው ጋር እኩል መሆኑን ይፈትሹ ፣ እውነት ሆኖ ከተገኘ ከዚያ ወደ ዙሩ ለማለፍ የበለጠ እንሄዳለን። ከአሁኑ ቁጥር ሁለት ጊዜ ጀምሮ እንጀምራለን እና ከፍተኛ መጠን ያለው እሴት እስከሚደርስ ድረስ እና ወደ እራሱ ብዜቶች እንሄዳለን እና ከዚያ ጀምሮ እያንዳንዱን እሴት ወደ ሐሰት እንጀምራለን ፡፡ ይህ አካሄድ በአጠቃላይ ይባላል የኢራቶስቴንስ ሲኢቭ.

የ 0 እሴት አስቀምጠናልth እና 1st የቅድመ-ፕራይም ድርድር ዋጋ እስከ 0. ስለዚህ የቅድመ-ፕራይም እና የዋና ድርድርን ለማቋረጥ ከ 2 እንጀምራለን ፡፡ ከዚያ ቀጣዩን የቅድመ-ፕራይም ድርድር ዋጋን ወደ ቀዳሚው የቅድመ-ፕራይም ድርድር እሴት እንገለብጠዋለን እና የዋናው ድርድር የአሁኑ ዋጋ እውነት መሆኑን ያረጋግጡ ፣ እውነት ከሆነ የቅድመ-ፕራይም ድርድር የአሁኑ ንጥረ ነገር እሴት ይጨምሩ ፡፡ ለእያንዳንዱ ጥያቄ እንደ መነሻ ቁጥር እና እንደ ማብቂያ ቁጥር እንቀበላለን ፡፡ የቅድመ-ፕራይም [የቀኝ] እና የቅድመ-ፕራይም [ግራ -1] ልዩነት እንመልሳለን። ያ የሚፈለገው መልስ ይሆናል ፡፡

ኮድ

በክልሎች ውስጥ ፕራይሞችን ለመቁጠር በ C + + ውስጥ ተግባራዊነት

#include<iostream>
#include<stdio.h>
#include<cstring>

using namespace std;

const int MAX = 10000;

int prePrime[MAX + 1];

void PrePrimeFunction ()
{

    bool prime[MAX + 1];
    memset(prime, true, sizeof(prime));

    for (int a = 2; a * a <= MAX; a ++)
    {
        if (prime[a] == true)
        {
            for (int i = a * 2; i <= MAX; i += a)
                prime[i] = false;
        }
    }
    prePrime[0] = prePrime[1] = 0;
    for (int q = 2; q <= MAX; q++)
    {
        prePrime[q] = prePrime[q - 1];
        if (prime[q])
            prePrime[q]++;
    }
}

int solveQuery(int L, int R)
{
    return prePrime[R] - ((L>0) ? prePrime[L - 1] : 0);
}

int main()
{
    PrePrimeFunction();

    int L = 4, R = 10;
    cout << solveQuery(L, R) << endl;

    L = 6, R = 8;
    cout << solveQuery(L, R) << endl;

    return 0;
}
2
1

በክልሎች ውስጥ ዋና ጊዜዎችን ለመቁጠር በጃቫ ውስጥ መተግበር

import java.util.Arrays;

class PrimeInRange
{

    static final int MAX = 10000;

    static int prePrime[] = new int[MAX + 1];

    static void PrePrimeFunction()
    {

        boolean prime[] = new boolean[MAX + 1];
        Arrays.fill(prime, true);

        for (int a = 2; a * a <= MAX; a++)
        {
            if (prime[a] == true)
            {

                for (int i = a * 2; i <= MAX; i += a)
                    prime[i] = false;
            }
        }

        prePrime[0] = prePrime[1] = 0;

        for (int q = 2; q <= MAX; q++)
        {
            prePrime[q] = prePrime[q - 1];
            if (prime[q])
                prePrime[q]++;
        }
    }

    static int solveQuery(int L, int R)
    {
        return prePrime[R] - ((L>0) ? prePrime[L - 1] : 0);
    }

    public static void main(String[] args)
    {
        PrePrimeFunction();
        int L = 4, R = 10;
        System.out.println(solveQuery(L, R));

        L = 6;
        R = 8;
        System.out.println(solveQuery(L, R));
    }
}
2
1

ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (n * መዝገብ (መዝገብ (n)) + q) የት “N” በድርድሩ ውስጥ ያሉት ንጥረ ነገሮች ብዛት ነው እና "Q" የጥያቄዎች ብዛት ነው። ስለሆነም ይህ ጊዜ ውስብስብነት “Srave of Eratosthenes” በተጠቀምንበት ስልተ ቀመር ምክንያት ነው።

የቦታ ውስብስብነት

ኦ (1) ምክንያቱም የድርድሩ መጠን በግብዓት ላይ የተመሠረተ ስላልሆነ ከቋሚ እሴት ጋር እኩል ነው። ምክንያቱም የትርፍ ጊዜዎቹን ውጤት ለማከማቸት ቦታ ያስፈልጋል ፡፡ ቁጥሩ ዋና ወይም ያልሆነ ከሆነ የምናከማች ስለሆነ ፡፡