ശ്രേണികളിലെ പ്രൈമുകളുടെ എണ്ണം


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ഗൂഗിൾ ഉയർത്തൽ കുലിസ അരിപ്പ 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] എന്നിവയുടെ വ്യത്യാസം ഞങ്ങൾ നൽകും. അത് ആവശ്യമായ ഉത്തരമായിരിക്കും.

കോഡ്

ശ്രേണികളിലെ പ്രൈമുകൾ എണ്ണുന്നതിന് സി ++ ൽ നടപ്പിലാക്കൽ

#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 * ലോഗ് (ലോഗ് (n)) + q) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം കൂടാതെ "Q" ചോദ്യങ്ങളുടെ എണ്ണം. ഈ സമയത്തെ സങ്കീർണ്ണത കാരണം “എറാത്തോസ്റ്റീനസ് അരിപ്പ” ഞങ്ങൾ ഉപയോഗിച്ച അൽഗോരിതം ആണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1) അറേയുടെ വലുപ്പം ഇൻ‌പുട്ടിനെ ആശ്രയിക്കുന്നില്ല എന്നതിനാൽ ഇത് ഒരു സ്ഥിര മൂല്യത്തിന് തുല്യമാണ്. പ്രൈമുകളുടെ ഫലം സംഭരിക്കാൻ സ്ഥലം ആവശ്യമാണ്. നമ്പർ പ്രൈം ആണോ ഇല്ലയോ എന്ന് ഞങ്ങൾ സംഭരിക്കുന്നതിനാൽ.