SPOČÍTAJTE ČÍSLA Z DANÉHO ROZSAHU, KTORÉ MAJÚ PRESNE 5 RÔZNYCH FAKTOROV

Dané dve celé čísla L a R , úlohou je vypočítať počet čísel z rozsahu [L, R] mať presne 5 rôznych pozitívnych faktorov.

Príklady:

Vstup: L = 1, R = 100
Výkon: 2
Vysvetlenie: Jediné dve čísla v rozsahu [1, 100], ktoré majú presne 5 rôznych faktorov, sú 16 a 81.
Faktory 16 sú {1, 2, 4, 8, 16}.
Faktory 81 sú {1, 3, 9, 27, 81}.

Vstup: L = 1, R = 100
Výkon: 2

Naivný prístup: Najjednoduchší spôsob riešenia tohto problému je prejsť cez rozsah [L, R] a pre každé číslo spočítajte jeho faktory. Ak sa počet faktorov rovná 5 , zvýšenie počtu o 1 .
Časová zložitosť: (R – L) × ?N
Pomocný priestor: O(1)
Efektívny prístup: Na optimalizáciu vyššie uvedeného prístupu je potrebné urobiť nasledujúce pozorovanie týkajúce sa čísel, ktoré majú presne 5 faktorov.

Nech je prvočíselný rozklad čísla p ₁ ^a _¹×p ₂ ^a _²× … ×p _n ^a _ⁿ.
Preto počet faktorov tohto čísla možno zapísať ako (a ₁+ 1)×(a ₂+ 1)× …×(a _n+ 1).
Pretože tento produkt sa musí rovnať 5 (čo je a prvočíslo ), v produkte musí existovať iba jeden výraz väčší ako 1. Tento výraz sa musí rovnať 5.
Preto ak a _i+ 1 = 5
=> a _i= 4

Pri riešení problému postupujte podľa nasledujúcich krokov:

Požadovaný počet je počet čísel v rozsahu obsahujúcom p ⁴ako faktor, kde p je prvočíslo.
Pre efektívny výpočet p ⁴pre veľký rozsah ( [1, 10 ¹⁸] ), myšlienkou je použiť Eratosthenove sito na uloženie všetkých prvočísel až do 10 ^4.5.

Nižšie je uvedená implementácia vyššie uvedeného prístupu:

C++14

// C++ Program to implement> // the above approach> #include> using> namespace> std;> const> int> N = 2e5;> // Stores all prime numbers> // up to 2 * 10^5> vector <> long> long> >prvočíslo;> // Function to generate all prime> // numbers up to 2 * 10 ^ 5 using> // Sieve of Eratosthenes> void> Sieve()> {> > prime.clear();> > vector <> bool> >p(N + 1,> true> );> > // Mark 0 and 1 as non-prime> > p[0] = p[1] => false> ;> > for> (> int> i = 2; i * i <= N; i++) {> > // If i is prime> > if> (p[i] ==> true> ) {> > // Mark all its factors as non-prime> > for> (> int> j = i * i; j <= N; j += i) {> > p[j] => false> ;> > }> > }> > }> > for> (> int>

i = 1; i   // If current number is prime  if (p[i]) {  // Store the prime  prime.push_back(1LL * pow(i, 4));  }  } } // Function to count numbers in the // range [L, R] having exactly 5 factors void countNumbers(long long int L,  long long int R) {  // Stores the required count  int Count = 0;  for (int p : prime) {  if (p>= L && str <= R) {  Count++;  }  }  cout  < < Count  < < endl; } // Driver Code int main() {  long long L = 16, R = 85000;  Sieve();  countNumbers(L, R);  return 0; }>

Java

// Java Program to implement> // the above approach> import> java.util.*;> class> GFG> {> > static> int> N => 200000> ;> > // Stores all prime numbers> > // up to 2 * 10^5> > static> int> prime[] => new> int> [> 20000> ];> > static> int> index => 0> ;> > // Function to generate all prime> > // numbers up to 2 * 10 ^ 5 using> > // Sieve of Eratosthenes> > static> void> Sieve()> > {> > index => 0> ;> > int> p[] => new> int> [N +> 1> ];> > for> (> int> i => 0> ; i <= N; i++)> > {> > p[i] => 1> ;> > }> > // Mark 0 and 1 as non-prime> > p[> 0> ] = p[> 1> ] => 0> ;> > for> (> int> i => 2> ; i * i <= N; i++)> > {> > // If i is prime> > if> (p[i] ==> 1> )> > {> > // Mark all its factors as non-prime> > for> (> int> j = i * i; j <= N; j += i)> > {> > p[j] => 0> ;> > }> > }> > }> > for> (> int> i => 1>

; i   {  // If current number is prime  if (p[i] == 1)  {  // Store the prime  prime[index++] = (int)(Math.pow(i, 4));  }  }  }  // Function to count numbers in the  // range [L, R] having exactly 5 factors  static void countNumbers(int L,int R)  {  // Stores the required count  int Count = 0;  for(int i = 0; i   {  int p = prime[i];  if (p>= L && str <= R)  {  Count++;  }  }  System.out.println(Count);  }  // Driver Code  public static void main(String[] args)   {  int L = 16, R = 85000;  Sieve();  countNumbers(L, R);  } } // This code is contributed by amreshkumar3.>

Python3

# Python3 implementation of> # the above approach> N> => 2> *> 100000> # Stores all prime numbers> # up to 2 * 10^5> prime> => [> 0> ]> *> N> # Function to generate all prime> # numbers up to 2 * 10 ^ 5 using> # Sieve of Eratosthenes> def> Sieve() :> > p> => [> True> ]> *> (N> +> 1> )> > # Mark 0 and 1 as non-prime> > p[> 0> ]> => p[> 1> ]> => False> > i> => 2> > while> (i> *> i <> => N) :> > # If i is prime> > if> (p[i]> => => True> ) :> > # Mark all its factors as non-prime> > for> j> in> range> (i> *> i, N, i):> > p[j]> => False> > i> +> => 1> > for> i> in> range> (N):> > # If current number is prime> > if> (p[i] !> => False> ) :> > # Store the prime> > prime.append(> pow> (i,> 4> ))> # Function to count numbers in the> # range [L, R] having exactly 5 factors> def> countNumbers(L, R) :> > # Stores the required count> > Count> => 0> > for> p> in> prime :> > if> (p>> => L> and> p <> => R) :> > Count> +> => 1> > print> (Count)> # Driver Code> L> => 16> R> => 85000> Sieve()> countNumbers(L, R)> # This code is contributed by code_hunt.>

C#

// C# Program to implement> // the above approach> using> System;> class> GFG> {> > static> int> N = 200000;> > // Stores all prime numbers> > // up to 2 * 10^5> > static> int> []prime => new> int> [20000];> > static> int> index = 0;> > // Function to generate all prime> > // numbers up to 2 * 10 ^ 5 using> > // Sieve of Eratosthenes> > static> void> Sieve()> > {> > index = 0;> > int> []p => new> int> [N + 1];> > for> (> int> i = 0; i <= N; i++)> > {> > p[i] = 1;> > }> > // Mark 0 and 1 as non-prime> > p[0] = p[1] = 0;> > for> (> int> i = 2; i * i <= N; i++)> > {> > // If i is prime> > if> (p[i] == 1)> > {> > // Mark all its factors as non-prime> > for> (> int> j = i * i; j <= N; j += i)> > {> > p[j] = 0;> > }> > }> > }> > for> (> int>

i = 1; i   {  // If current number is prime  if (p[i] == 1)  {  // Store the prime  prime[index++] = (int)(Math.Pow(i, 4));  }  }  }  // Function to count numbers in the  // range [L, R] having exactly 5 factors  static void countNumbers(int L,int R)  {  // Stores the required count  int Count = 0;  for(int i = 0; i   {  int p = prime[i];  if (p>= L && str <= R)  {  Count++;  }  }  Console.WriteLine(Count);  }  // Driver Code  public static void Main(String[] args)   {  int L = 16, R = 85000;  Sieve();  countNumbers(L, R);  } } // This code is contributed by shikhasingrajput>

Javascript

> // javascript program of the above approach> let N = 200000;> > > // Stores all prime numbers> > // up to 2 * 10^5> > let prime => new> Array(20000).fill(0);> > let index = 0;> > > // Function to generate all prime> > // numbers up to 2 * 10 ^ 5 using> > // Sieve of Eratosthenes> > function> Sieve()> > {> > index = 0;> > let p => new> Array (N + 1).fill(0);> > for> (let i = 0; i <= N; i++)> > {> > p[i] = 1;> > }> > > // Mark 0 and 1 as non-prime> > p[0] = p[1] = 0;> > for> (let i = 2; i * i <= N; i++)> > {> > > // If i is prime> > if> (p[i] == 1)> > {> > > // Mark all its factors as non-prime> > for> (let j = i * i; j <= N; j += i)> > {> > p[j] = 0;> > }> > }> > }> > for>

(let i = 1; i   {    // If current number is prime  if (p[i] == 1)  {    // Store the prime  prime[index++] = (Math.pow(i, 4));  }  }  }    // Function to count numbers in the  // range [L, R] having exactly 5 factors  function countNumbers(L, R)  {    // Stores the required count  let Count = 0;  for(let i = 0; i   {  let p = prime[i];  if (p>= L && str <= R)  {  Count++;  }  }  document.write(Count);  }  // Driver Code    let L = 16, R = 85000;  Sieve();  countNumbers(L, R);>

Výkon:

Časová zložitosť: O(N * log(log(N)) )
Pomocný priestor: O(N)