Пресметајте ги прстите во опсег


Ниво на тешкотија Медиум
Често прашувано во Google Крстоносните Кулиза Ситот 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. За секое барање вратете ја разликата во prePrime [десно] и prePrime [лево-1].

Објаснување

Даден е опсег на број како почетен и завршен број. Така, разгледувајќи го овој опсег бидејќи е исполнет со сите меѓу-броеви. Побаравме да го откриеме вкупниот број на прости броеви во овој опсег. За ова, ќе градиме низа пред-премија преку која ќе можеме да решиме кое било прашање во рамките на максималниот број. Прогласете цел ред со максимална големина од 10000 што ни е даден, и со иста големина, ќе прогласиме Булова низа од којашто иницијализиравме како вредност за вистинита.

Поминувајте во јамка од вредноста два затоа што не можеме да го сметаме еден како прост број. Проверете го секој број на Булова примарна низа дали секоја вредност е еднаква на вистинската, ако се утврди дека е точна, тогаш ќе се движиме понатаму за да поминеме во јамка. Startе започнеме од двојно повеќе од тековниот број и ќе се придвижиме напред до неговите множители сè додека не се достигне вредноста на максималната големина и да се иницијализира секоја вредност од тогаш на неточна. Овој пристап обично се нарекува како Сито од Ератостен.

Ние ја поставуваме вредноста на 0th и 1st вредност на низата prePrime до 0. Така што ќе започнеме од 2 за да ја поминеме низата prePrime и primer. Потоа ја копираме следната вредност на низата prePrime на претходната вредност на низата prePrime и проверуваме дали моменталната вредност на главната низа е точна, ако е точна, тогаш ја зголемуваме вредноста на тековниот елемент на низата prePrime. За секое барање ќе добиеме како почетен и завршен број. Willе ја вратиме разликата во 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

Имплементација во Јава за броење на почетните вредности во опсези

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) каде „Н“ е бројот на елементи во низата и "Q" е бројот на пребарувања. Така, оваа сложеност во времето е поради алгоритмот што го користевме „Сито од Ератостен“.

Комплексноста на просторот

О (1) бидејќи големината на низата не зависи од влезот, таа е еднаква на постојаната вредност. Бидејќи е потребен простор за складирање на резултатот од почетните вредности. Бидејќи чуваме дали бројот е прост или не.