2

我正在研究 Interview Street 的“Unfriendly Numbers”谜题。

它是这样的：

给定一个整数和另一个整数列表，找出仅对给定整数唯一且不与其他整数列表共享的因子。

因此，如果集合 1（集合 Y）是（并且 n 是给定的数字）：

∃Y{z|n % z = 0}

基本上：每个 z 都有一个 Y，其中 z 是一个数字，其中 n % z 为 0。

我们想要 Y 的集合差减去包含其他数字列表的所有因子的集合。

那么你将如何处理这个问题？

求整数 n 的因数？其他数字的所有因素，只是剔除非唯一因素？

或者你会只找到 n 的因子，然后用它们来划分其他数字并剔除非唯一的数字吗？

或者有没有办法在不考虑数字的情况下做到这一点？

到目前为止，我已经使用了 Trial Division、Pollard 的 Rho、Brent 的 Pollard 的 Rho 变体和 Fermat 的因式分解方法。我还使用了 Lucas-Lehmer 素性检验和 Euclids GCD。

但到目前为止，什么都没有，只是错误答案的组合或超过了时间限制。一个已知的解决方案据称涉及轮初筛，但我不确定那是什么。

不管怎么说，多谢拉。

4

1 回答 1

0

让你的列表大小为 x，数字为 n。然后期望 x* sqrt(n) 的时间复杂度

1-找到所有素数直到 n 的 sqrt

2-对于除n但列表中没有元素的每个素数，添加到结果集中

3- 返回结果集

public static List<Integer> uniqueFactors(int n, int[] list){
    //find possible prime factors of n: O(sqrt(n))
    int factors = (int)Math.sqrt(n);
    boolean [] P = new boolean[factors+1];
    Arrays.fill(P, true);
    P[0]=P[1]= false;//0 and 1 are not primes
    int limit =(int) Math.sqrt(factors)+1;//prime search limit
    for(int i=2; i <= limit; i++ )
        if(P[i]) {
            int y;
            for(int x=2; (y=x*i)<=factors; x++)
                if(P[y])
                    P[y]=false;
        }
    //retrieve/identify all prime factors of n that are not prime factors of elements in list
    //O is sqrt(n) * list
    List<Integer> result = new ArrayList<Integer>();
    for(int i=2; i<=factors; i++)
        if(P[i] && n%i==0) {//if i is prime and a factor of n
            boolean shared = false;
            for(int el: list)
                if(el%i==0) {
                    shared=true;
                    break;
                }
            if(!shared)
                result.add(i);
        }//if
    return result;
}//uniqueFactors

测试

public static void main(String[] args) {
    int n=2*3*5*7*11*13*17*19;
    int list[]= {8,9,25,98,121,38};
    System.out.println(uniqueFactors(n,list));
}

print out: [13, 17]

我运行的解决方案的所有其他变体仍然以 Big-O 结尾： sqrt(n) * list_size

于 2012-04-19T15:38:23.633 回答