பிரைம்களின் எண்ணிக்கை லீட்கோட் தீர்வுகள்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் ஆப்பிள் மூலதன ஒன்று கூகிள் மைக்ரோசாப்ட்
ஹேஷிங் கணித

இந்த சிக்கலில், எங்களுக்கு ஒரு முழு எண் வழங்கப்படுகிறது, N. இலக்கு N ஐ விட குறைவான எண்கள் முதன்மையானவை என்பதைக் கணக்கிடுவது. முழு எண் எதிர்மறையானது என்று கட்டுப்படுத்தப்பட்டுள்ளது.

உதாரணமாக

7
3
10
4

விளக்கம்

10 க்கும் குறைவான பிரைம்கள் 2, 3, 5 மற்றும் 7 ஆகும். எனவே, எண்ணிக்கை 4 ஆகும்.

அணுகுமுறை (முரட்டு படை)

N ஐ விடக் குறைவான ஒவ்வொரு முழு எண்ணையும் சரிபார்த்து, அவை பிரதானமாக இருந்தால் முடிவை அதிகரிப்பதே பொதுவான அணுகுமுறை. எடுத்துக்காட்டாக, N = 10 ஐக் கவனியுங்கள். இப்போது, ​​இந்த வரம்பில் எத்தனை ப்ரீம்கள் உள்ளன என்பதைக் கண்டறிய 2 முதல் N - 1 வரை ஒரு காசோலையை இயக்கலாம். ஆனால், இந்த அணுகுமுறைக்கு முழு வரம்பிலும் ஒரு முதன்மை சோதனை தேவைப்படுகிறது, [2, என் - 1].  எனவே, இது மெதுவாக உள்ளது.

இது போன்ற சில மேம்படுத்தல்களை நாங்கள் செய்யலாம்:

  1. 2 ஐத் தவிர ஒவ்வொரு பிரதான எண்ணும் ஒற்றைப்படை முழு எண். எனவே, பிறகு 2, ஒற்றைப்படை முழு எண்களை மட்டுமே நாங்கள் சரிபார்க்க முடியும்.
  2. ஒரு எண் முதன்மையானதா என்பதை நாம் சரிபார்க்கலாம் O (√N) வழிமுறையை மேம்படுத்துவதற்கான நேரம்.

இருப்பினும், இந்த கட்டுரையில் பின்னர் விவாதிக்கப்பட்ட ஒரு சிறந்த அணுகுமுறை எங்களிடம் உள்ளது.

அல்காரிதம்

  1. எண்ணிக்கை குறைவாக இருந்தால் 3, திரும்ப 0, 2 என்பது மிகச்சிறிய பிரதானமாகும்
  2. 3 முதல் அனைத்து எண்களையும் சரிபார்த்து ஒரு சுழற்சியை இயக்கவும்
  3. ஒரு எண், N முதன்மையானது என்றால்:
    • அது உள்ளது 2 மற்றும் இடையே பிரதான காரணிகள் .N
  4. எண் முதன்மையானது என்றால், அதிகரிப்பு முடிவு
  5. முடிவை அச்சிடுங்கள்

கவுண்ட் பிரைம்கள் லீட்கோட் தீர்வுகளை செயல்படுத்துதல்

சி ++ திட்டம்

#include <bits/stdc++.h>
using namespace std;

bool isPrime(int N)
{
    for(int i = 2 ; i * i <= N ; i++)
        if(N % i == 0)
            return false;
    return true;
}


int countPrimes(int N)
{
    if(N < 3)
        return 0;
    int cnt = 1;
    for(int i = 3 ; i < N ; i += 2)
        if(isPrime(i))
            cnt++;

    return cnt;
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

ஜாவா திட்டம்

class count_primes
{
    static boolean isPrime(int N)
    {
        for(int i = 2 ; i * i <= N ; i++)
            if(N % i == 0)
                return false;

        return true;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        int cnt = 1;//since number is atleast 3, 2 is a prime less than N
        for(int i = 3 ; i < N ; i += 2)
            if(isPrime(i))
                cnt++;
        return cnt;
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

கவுண்ட் ப்ரைம்களின் சிக்கலான பகுப்பாய்வு லீட்கோட் தீர்வுகள்

நேர சிக்கலானது

நாங்கள் ஒரு வளையத்தை இயக்குகிறோம் ந / 2 முறை. ஒவ்வொரு காசோலையிலும், சிக்கலான நேரம் O (N / 2) (சராசரியாக எடுத்துக்கொள்வது ந / 2) செலவிடப்படுகிறது. எனவே, இந்த வழிமுறையின் நேர சிக்கலானது O (N√N).

விண்வெளி சிக்கலானது

ஓ (1), நிலையான மாறிகளுக்கு நிலையான இடம் மட்டுமே பயன்படுத்தப்படுகிறது.

அணுகுமுறை (உகந்த முறை)

எந்த பிரதான எண்ணையும் கவனியுங்கள், சொல்லட்டும் 5, தன்னைத் தவிர 5 இன் அனைத்து மடங்குகளும் ஒருபோதும் பிரதானமாக இருக்க முடியாது என்பது உறுதி, ஏனெனில் அவை 5 ஐ அவற்றின் பிரதான காரணிகளில் ஒன்றாகக் கொண்டிருக்கும். இதேபோல், எல்லா எண்களையும் N ஐ விட குறைவாகவும், அதை விட அதிகமாகவும் சேமிக்க முடியும் 0

தி எரடோஸ்தீனஸின் சல்லடை N ஐ விட குறைவாக ப்ரைம்களைக் கண்டறிய ஒரு பண்டைய மற்றும் திறமையான வழிமுறை O (N) ஐ ஒதுக்க போதுமான அளவு N நினைவகத்தில் இடம். இது பிரதமரல்லாத எண்களை கலப்பு எனக் குறிப்பதன் மூலம் அவற்றை மீண்டும் நீக்குகிறது. அனைத்து கலவைகளும் குறிக்கப்பட்ட பிறகு, குறிக்கப்படாத எண்கள் முதன்மையானவை.

மேலும், நாம் ஒரு பூலியனை சேமிக்க வேண்டும் வரிசை நினைவக பயன்பாட்டிற்கான எந்த எண்ணும் குறிக்கப்பட்டுள்ளதா இல்லையா என்பதை சரிபார்க்க. எனவே, இது நாம் இருக்கும் ஒரு வழக்கு வர்த்தக நினைவகம் ஆஃப் சரியான நேரத்தில் மேம்படுத்தவும்.

பிரைம்களின் எண்ணிக்கை லீட்கோட் தீர்வுகள்

அல்காரிதம்

  1. பூலியன் வரிசையை பராமரிக்கவும் பிரதம அளவு சமம் என் - 1
  2. முதன்மை [] கலவைகளை குறிக்க மற்றும் இறுதியில் ப்ரைம்களை சரிபார்க்க பயன்படுகிறது
  3. ஒவ்வொரு முழு எண்ணின் முதன்மையையும் துவக்கவும் உண்மை. வழிமுறை அமைக்கிறது தவறான ஒவ்வொரு பிரதமரல்லாத எண்ணுக்கும்
  4. 2 முதல் தொடங்கி முழு எண்ணின் முதல் பெருக்கம் வரை தொடர்ச்சியான முழு எண்களின் சுழற்சியை இயக்கவும் N ஐ விட குறைவாக:
    • ஒவ்வொரு முழு எண் x க்கும், அது முதன்மை [x] ஐ உண்மையாகக் கொண்டிருந்தால், அதன் பலவற்றைக் குறிக்கவும் தவறான
    • இங்கே ஒவ்வொரு முழு எண்ணின் பல மடங்கு தொடங்குகிறது x * x x இன் மற்ற அனைத்து மடங்குகளும் ஏற்கனவே குறிக்கப்படாது.
  5. [2, N - 1] வரம்பில் எத்தனை எண்கள் உள்ளன என்பதை இறுதியாக சரிபார்க்கவும் உண்மை பிரதான அட்டவணையில்
  6. முடிவை அச்சிடுங்கள்

கவுண்ட் பிரைம்கள் லீட்கோட் தீர்வுகளை செயல்படுத்துதல்

சி ++ திட்டம்

#include <bits/stdc++.h>
using namespace std;

int sieve(int N)
{
    if(N < 3)
        return 0;

    int cnt = 0;
    bool prime[N];
    for(int i = 2 ; i < N ; i++)
        prime[i] = true;

    for(int i = 2 ; i * i < N ; i++)
    {
        if(prime[i])
            for(int j = i * i ; j < N ; j += i)
                prime[j] = false;
    }

    for(int i = 2 ; i < N ; i++)
        if(prime[i])
            cnt++;

    return cnt;
}

int countPrimes(int N)
{
    if(N < 3)
        return 0;
    return sieve(N);
}


int main()
{
    int N = 10;
    cout << countPrimes(N) << '\n';
}

ஜாவா திட்டம்

class count_primes
{
    static int sieve(int N)
    {
        if(N < 3)
            return 0;

        int cnt = 0;
        boolean[] prime= new boolean[N];
        for(int i = 2 ; i < N ; i++)
            prime[i] = true;

        for(int i = 2 ; i * i < N ; i++)
        {
            if(prime[i])
                for(int j = i * i ; j < N ; j += i)
                    prime[j] = false;
        }

        for(int i = 2 ; i < N ; i++)
            if(prime[i])
                cnt++;

        return cnt;
    }

    static int countPrimes(int N)
    {
        if(N < 3)
            return 0;
        return sieve(N);
    }

    public static void main(String args[])
    {
        int N = 10;
        System.out.println(countPrimes(N));
    }
}

4

கவுண்ட் ப்ரைம்களின் சிக்கலான பகுப்பாய்வு லீட்கோட் தீர்வுகள்

நேர சிக்கலானது

வழிமுறையின் சிக்கலானது O (Nlog (logN)). இதை இவ்வாறு நிரூபிக்க முடியும்:

ஒவ்வொரு முழு எண், எக்ஸ், நாம் ஒரு நேரத்தை செலவிடுகிறோம் என் / எக்ஸ் அதன் அனைத்து மடங்குகளையும் நீக்குகிறது.

எனவே, மொத்தத்தில் செலவழித்த நேரம்: N / 2 + N / 3 + N / 5 + N / 7 + ……

N ஐ பொதுவானதாக எடுத்துக்கொள்வது, டி (என்) = என் (1/2 + 1/3 + 1/5 + 1/7 +…). தொடரின் தொகை (1/2 + 1/3 + 1/5 + 1/7 +…) என நிரூபிக்க முடியும் பதிவு (logN).

எனவே, T (N) = Nlog (logN)

விண்வெளி சிக்கலானது

ஓ (என்), ஒரு எண் முதன்மையானதா இல்லையா என்பதை சேமிக்க ஒரு ஹாஷ் அட்டவணையை உருவாக்குவதால்.