පරාසයන්හි ප්‍රාථමික ගණනය කරන්න


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ගූගල් ඉහළ දැමීම කුලීසා පතුරු 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. PrePrime array හි පෙර දර්ශකයට අගය පිටපත් කර ප්‍රයිම් අරා හි වත්මන් අගය සත්‍යයට සමාන දැයි පරීක්ෂා කරන්න, ඉන්පසු prePrime හි අගය 1 කින් වැඩි කරන්න.
  7. සෑම විමසුමක් සඳහාම ප්‍රිප්‍රයිම් [දකුණේ] සහ ප්‍රීප්‍රයිම් [වමේ -1] හි වෙනස නැවත ලබා දේ.

පැහැදිලි කිරීම

ආරම්භක අංකයක් සහ අවසන් අංකයක් ලෙස අංකයක පරාසයක් ලබා දී ඇත. මේ අනුව මෙම පරාසය සලකා බලනුයේ එය අතර ඇති සියලුම සංඛ්‍යා වලින් පිරී ඇති බැවිනි. මෙම පරාසය තුළ ඇති මුළු ප්‍රාථමික සංඛ්‍යා ගණන සොයා ගැනීමට අපි ඉල්ලා සිටිමු. මේ සඳහා, අපි උපරිම සංඛ්‍යා පරාසය තුළ ඕනෑම විමසුමක් විසඳිය හැකි පූර්ව ප්‍රයිම් අරා එකක් ගොඩනඟමු. අපට ලබා දී ඇති උපරිම ප්‍රමාණයෙන් 10000 ක පූර්ණ සංඛ්‍යා සංඛ්‍යාවක් ප්‍රකාශ කරන්න, එම ප්‍රමාණය සමඟම, අපි ආරම්භ කළ අගය සත්‍යයක් ලෙස ආරම්භ කළ බූලියන් අරාව ප්‍රකාශ කරමු.

අගයේ අංක දෙකෙන් ලූපයක් හරහා ගමන් කරන්න. බූලියන් ප්‍රයිම් අරා හි එක් එක් අගය සත්‍යයට සමාන දැයි පරීක්ෂා කරන්න, එය සත්‍ය බව සොයාගත හොත්, අපි තව දුරටත් ලූපයක් හරහා ගමන් කරමු. අපි වත්මන් සංඛ්‍යාවෙන් දෙගුණයකින් ආරම්භ කර උපරිම ප්‍රමාණයේ අගය ළඟා වන තෙක් එහි ගුණකයන් වෙත ඉදිරියට ගොස් එක් එක් අගය එතැන් සිට අසත්‍යය දක්වා ආරම්භ කරමු. මෙම ප්‍රවේශය සාමාන්‍යයෙන් හැඳින්වෙන්නේ එරටොස්තීනස් පෙරනයක්.

අපි 0 හි අගය නියම කරමුth හා 1st prePrime array හි අගය 0 දක්වා. එබැවින් අපි 2 සිට ආරම්භ කරන්නේ prePrime සහ prime array හරහා ගමන් කිරීමට ය. ඉන්පසු අපි ප්‍රීප්‍රයිම් අරාවේ ඊලඟ අගය පෙරප්‍රයිම් අරාවේ පෙර වටිනාකමට පිටපත් කර ප්‍රයිම් අරා හි වත්මන් අගය සත්‍ය දැයි පරික්ෂා කරමු, සත්‍ය නම් ප්‍රිප්‍රයිම් අරාවේ වත්මන් මූලද්‍රව්‍යයේ අගය වැඩි කරන්න. සෑම විමසුමකටම අපට ආරම්භක අංකයක් සහ අවසන් අංකයක් ලැබෙනු ඇත. අපි ප්‍රීප්‍රයිම් [දකුණේ] සහ ප්‍රීප්‍රයිම් [වමේ -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 * log (ලොග් (n)) + q) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන සහ "Q" යනු විමසුම් ගණනයි. මේ වතාවේ සංකීර්ණතාවයට හේතුව අපි “එරටොස්තීනස් පෙරනයක්” භාවිතා කළ ඇල්ගොරිතමයයි.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (1) අරාවෙහි විශාලත්වය ආදානය මත රඳා නොපවතින බැවින් එය නියත අගයකට සමාන වේ. ප්‍රාථමිකයේ ප්‍රති result ලය ගබඩා කිරීමට අවකාශය අවශ්‍ය වන බැවිනි. අංකය ප්‍රමුඛද නැද්ද යන්න අප ගබඩා කරන බැවින්.