2

私は、Interview Street の「UnFriendly Numbers」パズルに取り組んでいます。

こんなふうになります：

与えられた整数と別の整数のリストから、与えられた整数にのみ固有であり、他の整数のリストと共有されていない係数を見つけます。

したがって、セット 1 (セット Y) が (および n が指定された数値である) 場合:

∃Y{z|n % z = 0}

基本的に: すべての z に Y があり、z は n % z が 0 の数値です。

Y の集合差から、他の数のリストのすべての因数を含む集合を差し引いたものが必要です。

では、これにどのようにアプローチしますか？

整数 n の因数を見つけますか? 他の数値のすべての要因と、一意ではない要因を除外するだけですか?

それとも、n の因数だけを見つけて、それらを使用して他の数を割り、一意でない数を除外しますか?

それとも素因数分解せずにやる方法ありますか？

ここまでは、試行分割、ポラードのロー、ブレントのポラードのローのバリエーション、フェルマーの因数分解法を使用してきました。Lucas-Lehmer primality test と Euclids GCD も利用しました。

しかし、これまでのところ、間違った答えの組み合わせまたは制限時間を超えているだけです。既知の解決策には、ホイール プライム シーブが関係していると思われますが、それが何であるかはわかりません。

とにかく、ありがとう。

4

1 に答える 1

0

リストのサイズを x、数を n とします。次に、 x* sqrt(n) の時間計算量を期待します

1-n の 2 乗までのすべての素数を見つける

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 に答える