java - 给定素数和指数，生成小于 N 的所有可能整数

Question

我正在寻找编写一个函数，给定一组指数和一组素数，它将生成所有可能的整数，这些整数可以使用给定集合中的素数形成，并将它们提升到给定指数集中的指数，限制整数不能超过限制N。素数集合包含的元素数量不少于指数集合中的元素数量。必须使用所有指数，并且它们不一定是不同的。质数集是排序的，指数列表也是如此，从小到大。

例如，假设我们的素数集是{11,19,29,31}。指数集是{1,4}和N = 20,000,000。所以，我们谈论的是令人满意的产品P = a^1*b^4。

P = 11^1 * 19^4 = 1,433,531

P = 11^1 * 29^4 = 7,780,091

P = 11^1 * 31^4 = 10,158,731

P = 19^1 * 29^4 = 13,438,339

P = 19^1 * 31^4 = 17,546,899

P = 29^1 * 31^4 = 26,782,109---- 由于限制限制而被丢弃

P = 19^1 * 11^4 = 278,179

P = 29^1 * 11^4 = 424,589

P = 29^1 * 19^4 = 3,779,309

P = 31^1 * 11^4 = 453,871

P = 31^1 * 19^4 = 4,039,951

P = 31^1 * 29^4 = 21,925,711---- 由于限制限制而被丢弃

请注意，每个素数都可以有任何指数，例如，较低的素数不必具有较低的指数，因为交换素数之间的指数会导致不同的整数。但是，如果指数集是{1,1}因为在任何 2 个素数之间交换它们不会改变结果 IE ，则情况并非如此11^1 * 31^1 = 31^1 * 11^1。

就我的目的而言，指数集包含很少的元素，大约5，但N非常大，超过10^13，并且素数集包含许多素数，可以50,000说。因此，有效地创建所有可能的整数是一项挑战。

我提出的代码使用递归。它生成所有可能的此类整数，并跟踪：一个表示指数集的数组列表，称为partition，used=我们当前产品中使用的指数数，partitionIndex=我们将在当前函数调用中使用的指数的索引，到目前为止我们使用的素数的数组列表 - primesUsed（以避免在产品中使用两次相同的素数）最后，prod= 我们当前的产品。used当与我们的指数列表一样大时，递归将停止，这意味着我们已经使用了所有指数并且我们的产品是可行的。当我们当前的乘积太大而无法乘以任何其他素数时，就会进行修剪。每个可行的整数都被添加到 的数组列表中products。这是代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class test3 {

    public static long N;
    public static long [] primes;
    public static ArrayList <Long> products;
    
    public static void main(String[] args) 
    {
        N = 20000000;
        primes = new long [] {11,19,29,31};
        products = new ArrayList <Long>();
        
        ArrayList <Long> partition = new ArrayList <Long>();
        partition.add(1L);
        partition.add(4L);
        
        generateProducts(partition , 0 , 0 , new ArrayList <Long>() , 1);
        
        //Set <Long> discardDups = new HashSet<>(products);   --- for list {1,4}, can be skipped.
        //products.clear();                                   --- but for {1,1} has to be used, otherwise there are duplicates
        //products.addAll(discardDups);
        
        Collections.sort(products);
        
        System.out.println(products);
        System.out.println(products.size());
    }
    
    public static void generateProducts (List <Long> partition , int used , int partitionIndex , ArrayList <Long> primesUsed , long prod)
    {
        if (used == partition.size())
        {
            products.add(prod);
            return;
        }

        for (int i = 0 ; i < primes.length && primes.length - i + 1 >= partition.size() - partitionIndex && prod * Math.pow(primes[i], partition.get(partitionIndex)) <= N ; i++)
        {
            if (!primesUsed.contains(primes[i]))
            {
                primesUsed.add(primes[i]);
                generateProducts(partition , used + 1 , partitionIndex + 1 , primesUsed , (long) (prod * Math.pow(primes[i], partition.get(partitionIndex))));
                primesUsed.remove(primesUsed.size() - 1);
            }
        }
    }

}

此功能的缺点是：

1. 它会生成许多重复项。因为函数中的计数器从0每次开始，并且它检查我们没有重用任何素数，所以当指数相同时，它会生成一个重复的，IE 它处理11^1 * 31^1不同31^1 * 11^1。

2. 该算法总体上需要很长时间。我再次假设，因为计数器一遍又一遍地从 0 开始。

我很清楚我可以使用 a 摆脱重复项，Set但这非常耗时。此外，跟踪使用的最高素数索引并在每次函数调用时从它开始会使算法更快，但不会生成具有较低指数的较大素数的产品。

我感兴趣的是一种有效生成所有此类产品的方法。我不确定我的代码是否可以更改为它。如果可以，那么它应该能够生成所有可能的此类整数，它应该首先避免生成重复，并且“停止”条件或修剪应该更好地保留尽可能多的冗余函数调用。

也许完全需要另一种方法，但目标保持不变。我将不胜感激任何关于如何更改我的代码以避免重复而不跳过任何可能的整数并使其更快的方向。如果无法避免重复，那么至少有一个方向如何减少函数调用的数量。任何其他实现相同目标的方法都是最受欢迎的！

标签： javaarraysalgorithmrecursioninteger