श्रेणींमध्ये पुरस्कारांची मोजणी करा


अडचण पातळी मध्यम
वारंवार विचारले Google वाढ कुलिझा चाळणी Snapchat याहू
गणित संख्या प्रणाली

समस्या विधान

"श्रेणींमध्ये प्रीमियम मोजा" या समस्येमध्ये असे म्हटले आहे की आपणास श्रेणी [डावीकडे, उजवीकडे] देण्यात आली आहे, जेथे 0 <= डावी <= उजवी <= 10000. समस्या विधान श्रेणीमधील मुख्य संख्येची एकूण संख्या शोधण्यास सांगते. असंख्य प्रश्न असतील असे गृहीत धरून.

उदाहरण

left: 4
right:10
2

स्पष्टीकरण

5 आणि 7 केवळ 2 प्रमुख संख्या आहेत.

श्रेणींमध्ये पुरस्कारांची मोजणी करा

left: 6
right:8
1

स्पष्टीकरण

ही एकमेव प्राथमिक संख्या आहे.

अल्गोरिदम

  1. एक तयार करा पूर्णांक अ‍ॅरे आणि बुलियन अ‍ॅरे 'प्राइम' जास्तीत जास्त दिलेल्या आकाराचे आणि बुलियन अ‍ॅरेसह प्रारंभ करा खरे.
  2. बुलियन अ‍ॅरेचा आढावा घ्या आणि सध्याचे प्राइमरी अ‍ॅरेचे मूल्य खरे आहे का ते तपासा.
  3. नंतर वर्तमान अ‍ॅरे घटकातून ट्रॅव्हर्सिंग प्रारंभ करा आणि प्रत्येक अ‍ॅरे घटक त्यापासून खोटे वर प्रारंभ करा जे वर्तमान घटकाच्या परिमाण समानतेच्या अंतरावर आहे. याचा अर्थ आम्ही सध्याच्या घटकाच्या गुणाकारांकडे जात आहोत.
  4. प्रीप्राइम [0] आणि प्रीप्राइम [1] ते 0 सेट करा.
  5. जास्तीत जास्त दिलेल्या मूल्यापर्यंत 2 वरून जा.
  6. प्रीप्राइम अ‍ॅरेच्या आधीच्या अनुक्रमणिकेवर मूल्य कॉपी करा आणि प्राइमरी अ‍ॅरेचे वर्तमान मूल्य बरोबर आहे का ते तपासा, तर प्रीप्राइमच्या मूल्याचे मूल्य 1 ने वाढवा.
  7. प्रत्येक क्वेरीसाठी प्रीप्राइम [उजवीकडे] आणि प्रीप्राइम [डावे -1] मधील फरक परत करा.

स्पष्टीकरण

सुरुवातीची संख्या आणि शेवटची संख्या म्हणून संख्येची श्रेणी दिली. अशा प्रकारे या श्रेणीचा विचार करा कारण ही सर्व इन-दरम्यान-संख्यांसह भरली आहे. आम्ही या श्रेणीतील मुख्य संख्येची संख्या शोधण्यास सांगितले आहे. यासाठी आम्ही प्रीप्राइम अ‍ॅरे बनवित आहोत ज्याद्वारे आम्ही कोणतीही क्वेरी जास्तीत जास्त संख्येच्या श्रेणीमध्ये सोडवू शकतो. आम्हाला दिलेला जास्तीत जास्त 10000 आकाराचा पूर्णांक अ‍ॅरे घोषित करा आणि त्याच आकारासह, आम्ही बुलियन अ‍ॅरे घोषित करू, ज्यापैकी आम्ही व्हॅल्यू ट्रू म्हणून आरंभ केला.

व्हॅल्यू दोन मधील पळवाट मध्ये जा कारण आपण एखाद्याला प्रथम क्रमांक मानू शकत नाही. बूलियन प्राइम rayरेची प्रत्येक संख्या बरोबर बरोबर असल्याचे तपासून पहा, जर ते खरे असल्याचे आढळले तर आपण लूपमध्ये ट्रॅव्हर्स वर जाऊ. आम्ही सध्याच्या संख्येच्या दुप्पटपासून प्रारंभ करू आणि जास्तीत जास्त आकाराचे मूल्य पर्यंत पोहोचेपर्यंत त्याच्या गुणाकारांकडे पुढे जाऊ आणि प्रत्येक मूल्यापासून प्रारंभ केल्यापासून ते खोट्या होऊ. हा दृष्टिकोन सामान्यतः म्हणून संदर्भित केला जातो एराटोस्थेनिस चाळणी.

आम्ही 0 ची व्हॅल्यू सेट केलीth आणि 1st प्रीप्राइम अ‍ॅरेची व्हॅल्यू 0 पर्यंत होईल. ज्यामुळे आपण प्रीप्राइम व प्राइम अ‍ॅरे 2 वरून सुरू करू. तर आपण प्रीप्राइम अ‍ॅरेची पुढील व्हॅल्यू प्रीप्राइम अ‍ॅरेच्या आधीच्या व्हॅल्यूमध्ये कॉपी करतो आणि प्राइम rayरेची सध्याची व्हॅल्यू बरोबर आहे का ते तपासून घेतल्यास प्रीप्राइम अ‍ॅरेच्या वर्तमान घटकाचे मूल्य वाढवते. प्रत्येक क्वेरीसाठी आम्हाला प्रारंभ क्रमांक आणि शेवटची संख्या म्हणून प्राप्त होईल. आम्ही प्रीप्राइम [उजवीकडे] आणि प्रीप्राइम [डावे -1] मधील फरक परत करू. ते आवश्यक उत्तर असेल.

कोड

श्रेणींमध्ये प्राइम मोजण्यासाठी सी ++ मध्ये अंमलबजावणी

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन * लॉग (लॉग (एन)) + क) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या आणि "Q" क्वेरींची संख्या आहे. अशाप्रकारे या वेळी जटिलता आम्ही “सिव्हि ऑफ एराटोस्थेनिस” वापरलेल्या अल्गोरिदममुळे आहे.

स्पेस कॉम्प्लेक्सिटी

ओ (1) कारण अ‍ॅरेचा आकार इनपुटवर अवलंबून नाही, तो स्थिर मूल्याच्या बरोबरीचा असतो. कारण प्राइम्सचा निकाल संग्रहित करण्यासाठी जागा आवश्यक आहे. संख्या संख्य आहे की नाही हे आम्ही संग्रहित करत आहोत.