Броји примесе у опсезима  


Ниво тешкоће Средњи
Често питани у гоогле Пешачење Кулиза Сиеве Снапцхат иахоо
Математика Нумбер Систем

Изјава о проблему  

Проблем „Бројање примера у опсезима“ наводи да вам се даје опсег [лево, десно], где је 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 који нам је дат, а истом величином ћемо прогласити логички низ чији смо иницијализовали као вредност тачно.

Види такође
Вертикални збир у датом бинарном стаблу

Пређите петљу из вредности две јер једну не можемо сматрати простим бројем. Проверите да ли је сваки број логичког основног низа свака вредност једнака тачној, ако се утврди да је тачна, онда ћемо се пребацити даље у петљу. Кренут ћемо од двоструког тренутног броја и кретаћемо се до његових вишекратника док се не достигне вредност максималне величине и иницијализовати сваку вредност од тада па надаље на фалсе. Овај приступ се обично назива Сито Ератостена.

Поставили смо вредност 0th и КСНУМКСst вредност преПриме низа на 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

Анализа сложености  

Сложеност времена

О (н * лог (лог (н)) + к) где „Н“ је број елемената у низу и "К" је број упита. Стога је овај пут сложеност због алгоритма који смо користили „Сито Ератостена“.

Види такође
Штампајте претке датог чвора бинарног стабла без рекурзије

Сложеност простора

О (1) јер величина низа не зависи од уноса, једнака је константној вредности. Јер је потребан простор за чување резултата простих бројева. Пошто чувамо да ли је број прост или не.