使用数组从质因数只有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# 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

输出如下：