வரம்புகளில் பிரதானங்களை எண்ணுங்கள்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது கூகிள் உயர்வு குலிசா சல்லடை SnapChat யாகூ
கணித எண் கணினி

சிக்கல் அறிக்கை

“வரம்புகளில் எண்ணிக்கையை மதிப்பிடு” என்ற சிக்கல் உங்களுக்கு ஒரு வரம்பை [இடது, வலது] வழங்கியுள்ளது, அங்கு 0 <= இடது <= வலது <= 10000. சிக்கல் அறிக்கை வரம்பிற்குள் உள்ள மொத்த பிரதான எண்களின் எண்ணிக்கையைக் கண்டறியக் கேட்கிறது. அதிக எண்ணிக்கையிலான கேள்விகள் இருக்கும் என்று வைத்துக் கொள்ளுங்கள்.

உதாரணமாக

left: 4
right:10
2

விளக்கம்

5 மற்றும் 7 மட்டுமே 2 பிரதான எண்கள்.

வரம்புகளில் பிரதானங்களை எண்ணுங்கள்

left: 6
right:8
1

விளக்கம்

7 மட்டுமே பிரதான எண்.

அல்காரிதம்

  1. உருவாக்கவும் முழு வரிசை மற்றும் பூலியன் வரிசை 'பிரதம' கொடுக்கப்பட்ட அதிகபட்ச அளவு மற்றும் பூலியன் வரிசையை துவக்கவும் உண்மை.
  2. பூலியன் வரிசைக்குச் சென்று, 'பிரைம்' வரிசையின் தற்போதைய மதிப்பு உண்மையா என்று சோதிக்கவும்.
  3. தற்போதைய வரிசை உறுப்பிலிருந்து பயணிக்கத் தொடங்கி, ஒவ்வொரு வரிசை உறுப்புகளையும் அப்போதிருந்து பொய்யாகத் தொடங்கவும், இது தற்போதைய உறுப்பின் அளவிற்கு சமமான தூரத்தில் இருக்கும். இதன் பொருள் நாம் தற்போதைய உறுப்பின் மடங்குகளுக்கு நகர்கிறோம்.
  4. PrePrime [0] மற்றும் prePrime [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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

O (n * log (log (n)) + q) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை மற்றும் "கே" என்பது வினவல்களின் எண்ணிக்கை. ஆகவே இந்த முறை சிக்கலானது “எரடோஸ்தீனஸின் சல்லடை” என்ற வழிமுறையைப் பயன்படுத்துவதால் தான்.

விண்வெளி சிக்கலானது

ஓ (1) வரிசையின் அளவு உள்ளீட்டைச் சார்ந்து இல்லை என்பதால், அது ஒரு நிலையான மதிப்புக்கு சமம். ப்ரைம்களின் முடிவைச் சேமிக்க இடம் தேவை என்பதால். எண் முதன்மையானதா இல்லையா என்பதை நாங்கள் சேமிப்பதால்.