Аралықтағы жай санақтарды санау


Күрделілік дәрежесі орта
Жиі кіреді Google жорық Кулиза Sieve Snapchat Yahoo
математика Сандар жүйесі

Проблемалық мәлімдеме

«Бастапқы санды диапазонда санау» есебінде сізге [солға, оңға] диапазон берілгендігі айтылған, мұндағы 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. PrePrime массивінің алдыңғы индексіне мәнді көшіріңіз және негізгі массивтің ағымдағы мәні шынға тең екендігін тексеріп, содан кейін prePrime мәнінің мәнін 1-ге арттырыңыз.
  7. Әрбір сұраныс үшін prePrime [оң жақ] және prePrime [сол жақ-1] айырмашылықтары қайтарылады.

Түсіндіру

Бастапқы және аяқталатын сан ретінде санның диапазоны берілген. Осылайша, бұл диапазонды барлық арасындағы сандармен толтырған кезде қарастырайық. Біз осы аралықта жай сандардың жалпы санын білуді сұрадық. Ол үшін біз кез-келген сұранысты максималды сан шеңберінде шеше алатын prePrime массивін құрамыз. Бізге берілген 10000 максималды бүтін массивті жариялаңыз, және сол өлшеммен біз инициализациялаған логикалық массивті ақиқат деп жариялаймыз.

Циклде екінші мәннен өтіңіз, өйткені біз оны жай сан ретінде қарастыра алмаймыз. Логикалық қарапайым массивтің әрбір санын тексеріңіз, егер оның мәні шынға тең болса, егер ол ақиқат деп табылса, онда біз цикл бойынша өту үшін әрі қарай жылжимыз. Ағымдағы санның екі есесінен бастаймыз және максималды өлшем мәніне жеткенге дейін оның еселіктеріне қарай жылжып, әрбір мәнді одан әрі жалғанға айналдырамыз. Бұл тәсіл жалпыға ортақ деп аталады Эратостен електері.

Біз 0 мәнін орнаттықth және 1st prePrime жиымының мәні 0-ге тең, осылайша біз 2-ден бастап prePrime және жай жиымға өтуді бастаймыз. Содан кейін біз prePrime массивінің келесі мәнін prePrime массивінің алдыңғы мәніне көшіреміз және негізгі массивтің ағымдағы мәні рас екенін тексереміз, егер true болса, онда prePrime массивінің ағымдағы элементінің мәнін көбейтеміз. Әрбір сұраныс үшін біз бастапқы және соңғы нөмір ретінде аламыз. Біз prePrime [оңға] және алдын ала [сол жақ-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

Java-да қарапайым сандарды санау үшін енгізу

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» - бұл массивтегі элементтер саны және «Q» - сұраныстар саны. Осылайша, бұл уақыттың күрделілігі біз «Эратосфен елегінен» қолданған алгоритмге байланысты.

Ғарыштың күрделілігі

O (1) массивтің мөлшері кіріске тәуелді емес болғандықтан, ол тұрақты мәнге тең. Жай санның нәтижесін сақтау үшін орын қажет. Нөмір жай немесе жоқ болса, біз оны сақтайтындықтан.