Аралыктардагы праймдарды эсептөө


Кыйынчылык деңгээли орто
Көп суралган Гугл селсаяктоо Кулиза Тандоо снэпчат Yahoo
Math Number System

Маселени билдирүү

"Праймдарды аралыктагы саноо" маселеси сизге [сол, оң] диапазону берилгенин, анда 0 <= сол <= оң <= 10000. Проблеманын берилиши аралыктагы жөнөкөй сандардын жалпы санын табууну суранат. Суроолор көп болот деп эсептесек.

мисал

left: 4
right:10
2

түшүндүрүү

5 жана 7 гана 2 жөнөкөй сандар.

Аралыктардагы праймдарды эсептөө

left: 6
right:8
1

түшүндүрүү

7 - бул жөнөкөй сан.

Algorithm

  1. түзүү үчүн бүтүн массив жана логикалык массив "премьер" логикалык массивди максималдуу чоңойтуп, инициализациялайт чыныгы.
  2. Логикалык массивди айланып өтүп, "жөнөкөй" массивдин учурдагы мааниси туура экендигин текшерип алыңыз.
  3. Андан кийин учурдагы массив элементинен өтүүнү баштаңыз жана ар бир массив элементин учурдан баштап жалганга учурдагы элементтин чоңдугуна барабар аралыкта баштаңыз. Бул учурдагы элементтин көбөйтүүлөрүнө өтүп жатабыз дегенди билдирет.
  4. PrePrime [0] жана prePrime [1] ден 0 деп кой.
  5. Максималдуу берилген мааниге чейин 2ден өтүңүз.
  6. Маанайды prePrime массивинин мурунку индексине көчүрүп, негизги массивдин учурдагы мааниси true менен барабар экендигин текшерип, андан кийин prePrime маанисинин маанисин 1ге көбөйтүңүз.
  7. Ар бир суроо үчүн prePrime [оң] жана prePrime [сол-1] айырмасын кайтарыңыз.

түшүндүрүү

Сандын диапазону баштапкы жана аяктоочу номери катары берилген. Ошентип, бул аралыктагы бардык сандар менен толтурулгандыктан, ушул диапазонду карап көрөлү. Ушул аралыктагы жөнөкөй сандардын жалпы санын табууну сурандык. Бул үчүн биз PrePrime массивин курабыз, анын жардамы менен биз каалаган суроону максималдуу сандын чегинде чече алабыз. Бизге берилген 10000 максималдуу бүтүн массивди жарыялаңыз, жана ошол эле көлөмдө биз инвализациялаган логикалык массивди чыныгы деп жарыялайбыз.

Эки чоңдуктан цикл менен өтүңүз, анткени бирөөнү жөнөкөй сан деп эсептей албайбыз. Логикалык башкы массивдин ар бир санын текшерип, анын мааниси барабар, эгер ал чын деп табылса, анда цикл менен өтүү үчүн андан ары жылабыз. Учурдагы сандын экиден баштап, анын чоңдугуна, эң чоң чоңдуктун маанисине жеткенге чейин, андан кийин ар бир маанини жалганга чейин баштайбыз. Бул ыкма жалпысынан деп аталат Эратосфендин элеги.

0 маанисин койдукth жана 1st prePrime массивинин мааниси 0. Ошентип, биз 2ден баштап, prePrime жана жөнөкөй массивди аралай баштайбыз. Андан кийин prePrime массивинин кийинки маанисин prePrime массивинин мурунку маанисине көчүрөбүз жана негизги массивдин учурдагы мааниси чын экендигин текшеребиз, эгер true болсо, анда 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) кайда "N" массивдеги элементтердин саны жана "С" сурамдардын саны. Ошентип, бул убакыттын татаалдыгы биз "Эретосфендин калбырын" колдонгон алгоритмге байланыштуу.

Космостун татаалдыгы

O (1) анткени массивдин көлөмү киргизүүгө көз каранды эмес, ал туруктуу мааниге барабар. Анткени жөнөкөй жыйынтыктарды сактоо үчүн орун талап кылынат. Номер жөнөкөй болсо дагы, болбосо дагы сактайбыз.