使用数组从质因数只有2和3的范围中计数数字|S2

本文概述

• C ++
• Java
• Python3
• C#

给定两个正整数L和R, 任务是计算范围内的元素[L, R]谁的主要因素只有2和3.

例子：

输入：L = 1, R = 10
输出：6
说明：2 = 2 3 = 3 4 = 2 * 2 6 = 2 * 3 8 = 2 * 2 * 2 9 = 3 * 3
输入：L = 100, R = 200
输出：5

有关更简单的方法, 请参阅计算主要因子仅为2和3的范围中的数字.

方法：

要以最佳方式解决问题, 请执行以下步骤：

• 储存2的所有幂哪个是小于或等于R排列成阵列power2 [].
• 同样, 存储3的所有幂小于或等于R在另一个数组中power3 [].
• 初始化第三个数组power23 []并存储每个元素的成对乘积power2 []与...的每个元素power3 []小于或等于[R.
• 现在适用于任何范围[L, R], 我们将简单地遍历数组power23 []并计算范围内的数字[L, R].

下面是上述方法的实现：

C ++

//C++ program to count the elements
//in the range [L, R] whose prime
//factors are only 2 and 3.
  
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
  
//Function which will calculate the
//elements in the given range
void calc_ans(ll l, ll r)
{
  
     vector<ll> power2, power3;
  
     //Store the current power of 2
     ll mul2 = 1;
     while (mul2 <= r) {
         power2.push_back(mul2);
         mul2 *= 2;
     }
  
     //Store the current power of 3
     ll mul3 = 1;
     while (mul3 <= r) {
         power3.push_back(mul3);
         mul3 *= 3;
     }
  
     //power23[] will store pairwise product of
     //elements of power2 and power3 that are <=r
     vector<ll> power23;
  
     for ( int x = 0; x <power2.size(); x++) {
         for ( int y = 0; y <power3.size(); y++) {
  
             ll mul = power2[x] * power3[y];
             if (mul == 1)
                 continue ;
  
             //Insert in power23][]
             //only if mul<=r
             if (mul <= r)
                 power23.push_back(mul);
         }
     }
  
     //Store the required answer
     ll ans = 0;
     for (ll x : power23) {
         if (x>= l && x <= r)
             ans++;
     }
  
     //Print the result
     cout <<ans <<endl;
}
  
//Driver code
int main()
{
  
     ll l = 1, r = 10;
  
     calc_ans(l, r);
  
     return 0;
}

Java

//Java program to count the elements
//in the range [L, R] whose prime
//factors are only 2 and 3.
import java.util.*;
class GFG{
  
//Function which will calculate the
//elements in the given range
static void calc_ans( int l, int r)
{
  
     Vector<Integer> power2 = new Vector<Integer>(), power3 = new Vector<Integer>();
  
     //Store the current power of 2
     int mul2 = 1 ;
     while (mul2 <= r)
     {
         power2.add(mul2);
         mul2 *= 2 ;
     }
  
     //Store the current power of 3
     int mul3 = 1 ;
     while (mul3 <= r) 
     {
         power3.add(mul3);
         mul3 *= 3 ;
     }
  
     //power23[] will store pairwise product of
     //elements of power2 and power3 that are <=r
     Vector<Integer> power23 = new Vector<Integer>();
  
     for ( int x = 0 ; x <power2.size(); x++)
     {
         for ( int y = 0 ; y <power3.size(); y++) 
         {
             int mul = power2.get(x) * 
                       power3.get(y);
             if (mul == 1 )
                 continue ;
  
             //Insert in power23][]
             //only if mul<=r
             if (mul <= r)
                 power23.add(mul);
         }
     }
  
     //Store the required answer
     int ans = 0 ;
     for ( int x : power23) 
     {
         if (x>= l && x <= r)
             ans++;
     }
  
     //Print the result
     System.out.print(ans + "\n" );
}
  
//Driver code
public static void main(String[] args)
{
     int l = 1 , r = 10 ;
  
     calc_ans(l, r);
}
}
  
//This code is contributed by 29AjayKumar

Python3

# Python3 program to count the elements 
# in the range [L, R] whose prime 
# factors are only 2 and 3. 
  
# Function which will calculate the 
# elements in the given range 
def calc_ans(l, r):
  
     power2 = []; power3 = []; 
  
     # Store the current power of 2 
     mul2 = 1 ; 
     while (mul2 <= r): 
         power2.append(mul2); 
         mul2 * = 2 ; 
  
     # Store the current power of 3 
     mul3 = 1 ; 
     while (mul3 <= r): 
         power3.append(mul3); 
         mul3 * = 3 ; 
  
     # power23[] will store pairwise 
     # product of elements of power2 
     # and power3 that are <=r 
     power23 = []; 
  
     for x in range ( len (power2)):
         for y in range ( len (power3)):
  
             mul = power2[x] * power3[y]; 
             if (mul = = 1 ):
                 continue ; 
  
             # Insert in power23][] 
             # only if mul<=r 
             if (mul <= r):
                 power23.append(mul); 
  
     # Store the required answer 
     ans = 0 ; 
     for x in power23:
         if (x> = l and x <= r):
             ans + = 1 ; 
  
     # Print the result 
     print (ans); 
  
# Driver code 
if __name__ = = "__main__" : 
  
     l = 1 ; r = 10 ;
      
     calc_ans(l, r); 
  
# This code is contributed by AnkitRai01

C#

//C# program to count the elements
//in the range [L, R] whose prime
//factors are only 2 and 3.
using System;
using System.Collections.Generic;
  
class GFG{
  
//Function which will calculate the
//elements in the given range
static void calc_ans( int l, int r)
{
  
     List<int> power2 = new List<int>(), power3 = new List<int>();
  
     //Store the current power of 2
     int mul2 = 1;
     while (mul2 <= r)
     {
         power2.Add(mul2);
         mul2 *= 2;
     }
  
     //Store the current power of 3
     int mul3 = 1;
     while (mul3 <= r) 
     {
         power3.Add(mul3);
         mul3 *= 3;
     }
  
     //power23[] will store pairwise product of
     //elements of power2 and power3 that are <=r
     List<int> power23 = new List<int>();
  
     for ( int x = 0; x <power2.Count; x++)
     {
         for ( int y = 0; y <power3.Count; y++) 
         {
             int mul = power2[x] * 
                       power3[y];
             if (mul == 1)
                 continue ;
  
             //Insert in power23, ]
             //only if mul<=r
             if (mul <= r)
                 power23.Add(mul);
         }
     }
  
     //Store the required answer
     int ans = 0;
     foreach ( int x in power23) 
     {
         if (x>= l && x <= r)
             ans++;
     }
  
     //Print the result
     Console.Write(ans + "\n" );
}
  
//Driver code
public static void Main(String[] args)
{
     int l = 1, r = 10;
  
     calc_ans(l, r);
}
}
  
//This code is contributed by 29AjayKumar

输出如下：

6

时间复杂度： O(Log2(R)*Log3(R))

注意：该方法可以进一步优化。存储2和3的幂后, 可以使用以下公式计算答案：两个指针而不是生成所有数字

---