Μετρήστε τους πρωταρχικούς κύκλους


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις Google Πεζοπορώ Κουλίζα Κόσκινο Snapchat Yahoo
μαθηματικά Αριθμός Σύστημα

Δήλωση προβλήματος

Το πρόβλημα "Count Primes in Ranges" δηλώνει ότι σας δίνεται ένα εύρος [αριστερά, δεξιά], όπου 0 <= αριστερά <= δεξιά <= 10000. Η δήλωση προβλήματος ζητά να μάθετε τον συνολικό αριθμό των πρώτων αριθμών εντός του εύρους. Υποθέτοντας ότι θα υπάρξει μεγάλος αριθμός ερωτημάτων.

Παράδειγμα

left: 4
right:10
2

εξήγηση

5 και 7 είναι οι μόνοι 2 πρώτοι αριθμοί.

Μετρήστε τους πρωταρχικούς κύκλους

left: 6
right:8
1

εξήγηση

7 είναι ο μόνος πρώτος αριθμός.

Αλγόριθμος

  1. Δημιουργία ενός ακέραιος αριθμός array και Boolean array 'πρωταρχικό' του μέγιστου δεδομένου μεγέθους και αρχικοποίηση του πίνακα Boolean με αληθής.
  2. Διασχίστε τον πίνακα Boolean και ελέγξτε αν η τρέχουσα τιμή του πίνακα "prime" είναι αληθής.
  3. Στη συνέχεια, ξεκινήστε να διασχίζετε από το τρέχον στοιχείο του πίνακα και αρχικοποιείτε κάθε στοιχείο του πίνακα από τότε και στο false που βρίσκεται σε απόσταση ίση με το μέγεθος του τρέχοντος στοιχείου. Αυτό σημαίνει ότι μετακινούμαστε στα πολλαπλάσια του τρέχοντος στοιχείου.
  4. Ορίστε prePrime [0] και prePrime [1] σε 0.
  5. Περάστε από το 2 έως τη μέγιστη δεδομένη τιμή.
  6. Αντιγράψτε την τιμή στον προηγούμενο ευρετήριο του πίνακα prePrime και ελέγξτε αν η τρέχουσα τιμή του πρωταρχικού πίνακα είναι ίση με την τιμή true και, στη συνέχεια, αυξήστε την τιμή της τιμής prePrime κατά 1.
  7. Για κάθε ερώτημα επιστρέψτε τη διαφορά prePrime [δεξιά] και prePrime [αριστερά-1].

εξήγηση

Δεδομένου εύρους αριθμού ως αρχικού και τελικού αριθμού. Εξετάζοντας έτσι αυτό το εύρος καθώς είναι γεμάτο με όλους τους ενδιάμεσους αριθμούς. Ζητήσαμε να μάθουμε τον συνολικό αριθμό των πρώτων αριθμών σε αυτό το εύρος. Γι 'αυτό, θα χτίσουμε έναν πίνακα προπληρωμής μέσω του οποίου μπορούμε να λύσουμε οποιοδήποτε ερώτημα εντός του εύρους του μέγιστου αριθμού. Δηλώστε έναν ακέραιο πίνακα μέγιστου μεγέθους 10000 που μας έχει δοθεί, και με το ίδιο μέγεθος, θα δηλώσουμε έναν πίνακα Boolean του οποίου αρχικοποιήσαμε ως τιμή true.

Περάστε σε έναν βρόχο από την τιμή δύο επειδή δεν μπορούμε να θεωρήσουμε έναν ως πρωταρχικό αριθμό. Ελέγξτε κάθε αριθμό του πρωταρχικού πίνακα Boolean κάθε τιμή είναι ίση με αληθινή, εάν βρεθεί ότι είναι αληθής, τότε θα προχωρήσουμε περαιτέρω για να περάσουμε σε ένα βρόχο. Θα ξεκινήσουμε από το διπλάσιο του τρέχοντος αριθμού και θα προχωρήσουμε στα πολλαπλάσια του έως ότου επιτευχθεί η τιμή του μέγιστου μεγέθους και αρχικοποιούμε κάθε τιμή από τότε και μετά σε false. Αυτή η προσέγγιση αναφέρεται γενικά ως Κόσκινο του Ερατοσθένη.

Ορίζουμε την τιμή 0th kai xxst τιμή του πίνακα 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

Υλοποίηση σε 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) όπου «Ν» είναι ο αριθμός των στοιχείων στον πίνακα και "Q" είναι ο αριθμός των ερωτημάτων. Έτσι, αυτή η χρονική πολυπλοκότητα οφείλεται στον αλγόριθμο που χρησιμοποιήσαμε το "Sieve of Eratosthenes".

Διαστημική πολυπλοκότητα

Ο (1) επειδή το μέγεθος του πίνακα δεν εξαρτάται από την είσοδο, είναι ίσο με μια σταθερή τιμή. Επειδή απαιτείται χώρος για την αποθήκευση του αποτελέσματος των πρώτων. Δεδομένου ότι αποθηκεύουμε εάν ο αριθμός είναι πρωταρχικός ή όχι.