დაითვალეთ პირველები დიაპაზონში


Რთული ტური საშუალო
ხშირად ეკითხებიან 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 მაქსიმალური ზომის მთელი რიგი, რომელიც მოცემულია ჩვენთვის, და იგივე ზომით, ჩვენ გამოვთქვამთ Boolean მასივს, რომლის ინიცირებაც, მნიშვნელობად ჭეშმარიტია.

გადაკვეთეთ მარყუჟით ორი მნიშვნელობიდან, რადგან ჩვენ არ შეგვიძლია განვიხილოთ იგი როგორც უბრალო რიცხვი. შეამოწმეთ ლოგიკური მასივის თითოეული რაოდენობის თითოეული მნიშვნელობა, უდრის true- ს, თუ სიმართლე აღმოჩნდა, მაშინ ჩვენ გადავდივართ მარყუჟის გადაკვეთაზე. ჩვენ დავიწყებთ ამჟამინდელი რიცხვის ორჯერ და მივდივართ მის ჯერადებამდე, სანამ არ მიიღწევა მაქსიმალური ზომა და თითოეული მნიშვნელობის ინიციალიზებას შემდეგ ხდება ცრუ. ამ მიდგომას ზოგადად მოიხსენიებენ, როგორც Eratosthenes- ის საჯინიბო.

ჩვენ ვადგენთ მნიშვნელობას 0th და 1st prePrime მასივის მნიშვნელობა 0.-მდე. ასე რომ, ჩვენ დავიწყებთ 2-დან prePrime და Prime მასივის გადაკვეთას. შემდეგ ჩვენ ვაკოპირებთ prePrime მასივის შემდეგ მნიშვნელობას prePrime მასივის წინა მნიშვნელობაზე და ვამოწმებთ, არის თუ არა ნამდვილი მასივის ამჟამინდელი მნიშვნელობა მართალი, თუ ასეა, შემდეგ გაზრდის prePrime მასივის მიმდინარე ელემენტს. თითოეული მოთხოვნისთვის მივიღებთ როგორც საწყისი რიცხვი, ისე დასრულებული ნომერი. ჩვენ დავაბრუნებთ 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" არის შეკითხვების რაოდენობა. ამრიგად, ამ დროის სირთულე არის ალგორითმის გამო, რომელიც ჩვენ გამოვიყენეთ "Eratosthenes Sieve".

სივრცის სირთულე

O (1) რადგან მასივის ზომა არ არის დამოკიდებული შეყვანაზე, ის ტოლია მუდმივ მნიშვნელობას. რადგან პირველ ადგილების შედეგის შესანახად საჭიროა სივრცე. ვინაიდან ჩვენ ვინახავთ თუ არა ნომერი მარტივი.