SKAITĪT SKAITĻUS NO NOTEIKTĀ DIAPAZONA AR PRECĪZI 5 ATŠĶIRĪGIEM FAKTORIEM

Doti divi veseli skaitļi L un R , uzdevums ir aprēķināt skaitļu skaitu no diapazona [L, R] kam tieši 5 atšķirīgi pozitīvi faktori.

Piemēri:

Ievade: L = 1, R = 100
Izvade: 2
Paskaidrojums: Vienīgie divi skaitļi diapazonā [1, 100] ar precīzi 5 atšķirīgiem faktoriem ir 16 un 81.
Koeficienti 16 ir {1, 2, 4, 8, 16}.
Koeficienti 81 ir {1, 3, 9, 27, 81}.
cietajos vākos pret mīkstajiem vākiem

Ievade: L = 1, R = 100
Izvade: 2

Naiva pieeja: Vienkāršākā pieeja šīs problēmas risināšanai ir šķērsot diapazonu [L, R] un katram skaitlim saskaitiet tā faktorus. Ja faktoru skaits ir vienāds ar 5 , skaita pieaugums par 1 .
Laika sarežģītība: (R – L) × ?N
Palīgtelpa: O(1)
Efektīva pieeja: Lai optimizētu iepriekš minēto pieeju, ir jāveic šāds novērojums attiecībā uz skaitļiem, kuriem ir tieši 5 faktori.

Lai skaitļa primārā faktorizācija ir p₁^a_¹×p₂^a_²× … × p_n^a_ⁿ.
Tāpēc šī skaitļa faktoru skaitu var uzrakstīt kā (a₁+ 1) × (a₂+ 1) × … × (a_n+ 1).
Tā kā šim produktam jābūt vienādam ar 5 (kas ir a pirmskaitlis ), produktā ir jābūt tikai vienam vārdam, kas ir lielāks par 1. Šim vārdam jābūt vienādam ar 5.
Tāpēc, ja a_i+ 1 = 5
=> a_i= 4

Lai atrisinātu problēmu, veiciet tālāk norādītās darbības.

Nepieciešamais skaits ir skaitļu skaits diapazonā, kas satur p⁴kā faktors, kur lpp ir pirmskaitlis.
Lai efektīvi aprēķinātu p⁴lielam diapazonam ( [1, 10¹⁸] ), ideja ir izmantot Eratosthenes sietu, lai saglabātu visus pirmskaitļus līdz 10^4.5.

Tālāk ir aprakstīta iepriekš minētās pieejas īstenošana.

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>>galvenais;> // 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 && lpp<= 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 && lpp<= 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.>

izlīdzināt css attēlu

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#

pievienot masīvā java

// 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 && lpp<= 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 && lpp<= R)  {  Count++;  }  }  document.write(Count);  }  // Driver Code    let L = 16, R = 85000;  Sieve();  countNumbers(L, R);>

Izvade:

7>

Laika sarežģītība: O(N * log(log(N)))
Palīgtelpa: O(N)

TechCodeview

Saskaitiet skaitļus no noteiktā diapazona, kam ir tieši 5 atšķirīgi faktori