ಶ್ರೇಣಿಗಳಲ್ಲಿ ಅವಿಭಾಜ್ಯಗಳನ್ನು ಎಣಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಗೂಗಲ್ ಪಾದಯಾತ್ರೆ ಕುಲಿಜಾ ಜರಡಿ Snapchat ಯಾಹೂ
ಮಠ ಸಂಖ್ಯೆ ವ್ಯವಸ್ಥೆ

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“ಶ್ರೇಣಿಗಳಲ್ಲಿ ಅವಿಭಾಜ್ಯಗಳನ್ನು ಎಣಿಸು” ಎಂಬ ಸಮಸ್ಯೆಯು ನಿಮಗೆ ಒಂದು ಶ್ರೇಣಿಯನ್ನು [ಎಡ, ಬಲ] ನೀಡಲಾಗಿದೆ, ಅಲ್ಲಿ 0 <= ಎಡ <= ಬಲ <= 10000. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ವ್ಯಾಪ್ತಿಯೊಳಗಿನ ಒಟ್ಟು ಅವಿಭಾಜ್ಯ ಸಂಖ್ಯೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ. ಹೆಚ್ಚಿನ ಸಂಖ್ಯೆಯ ಪ್ರಶ್ನೆಗಳು ಇರುತ್ತವೆ ಎಂದು uming ಹಿಸಿ.

ಉದಾಹರಣೆ

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] ನ ವ್ಯತ್ಯಾಸವನ್ನು ನಾವು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ. ಅದು ಅಗತ್ಯವಾದ ಉತ್ತರವಾಗಿರುತ್ತದೆ.

ಕೋಡ್

ಶ್ರೇಣಿಗಳಲ್ಲಿ ಅವಿಭಾಜ್ಯಗಳನ್ನು ಎಣಿಸಲು ಸಿ ++ ನಲ್ಲಿ ಅನುಷ್ಠಾನ

#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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

O (n * log (log (n)) + q) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ ಮತ್ತು "ಪ್ರಶ್ನೆ" ಪ್ರಶ್ನೆಗಳ ಸಂಖ್ಯೆ. ಆದ್ದರಿಂದ ಈ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ನಾವು "ಎರಾಟೋಸ್ಥೆನಸ್ ಜರಡಿ" ಅನ್ನು ಬಳಸಿದ ಅಲ್ಗಾರಿದಮ್ನ ಕಾರಣದಿಂದಾಗಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1) ರಚನೆಯ ಗಾತ್ರವು ಇನ್ಪುಟ್ ಅನ್ನು ಅವಲಂಬಿಸಿಲ್ಲವಾದ್ದರಿಂದ, ಅದು ಸ್ಥಿರ ಮೌಲ್ಯಕ್ಕೆ ಸಮಾನವಾಗಿರುತ್ತದೆ. ಏಕೆಂದರೆ ಅವಿಭಾಜ್ಯಗಳ ಫಲಿತಾಂಶವನ್ನು ಸಂಗ್ರಹಿಸಲು ಸ್ಥಳಾವಕಾಶ ಬೇಕಾಗುತ್ತದೆ. ಸಂಖ್ಯೆ ಅವಿಭಾಜ್ಯವಾಗಿದೆಯೋ ಇಲ್ಲವೋ ಎಂದು ನಾವು ಸಂಗ್ರಹಿಸುತ್ತೇವೆ.