このパズルにどのようにアプローチしますか？ （番号のユニークな要素を見つけること）

Question

私はInterview Streetの "Unfriendly Numbers"パズルに取り組んでいます。

それはこのように書き：指定された整数にのみ一意である要因を見つけ、整数、および整数の別のリストを考えると

、および整数の他のリストと共有されていません。

に設定1（Yセット）である（そしてnは所定の数である）場合：

∃Y{Z | N％のZ = 0}基本的

：Yは、すべてのZのためにそこにありますここで、zはn％zが0の数です。

他の数字のリストのすべての要素を含むセットからYの差を求めます。

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

整数nの係数を見つける？他の数字のすべての要因だけでなく、非ユニークな要因を取り除く？

あなたはnの因子を見つけて、それらを使って他の数を分け、非固有のものを除外しますか？

番号を考慮せずに行う方法はありますか？

これまでのところ、PollardのRhoのTrial Division、PollardのRhoのBrentのバリ​​エーション、Fermatの分解法を使用しました。私はまた、Lucas-Lehmer素数性テストとユークリッドGCDを利用しました。

これまでのところ、何もせず、間違った回答や期限を超過したものだけです。知られている解決策はホイールプライム篩に関係すると思われますが、私はそれが何であるか不明です。

ありがとうございました。

Answer 1

リストのサイズをxとし、数字をnとします。次いで

が

1-見つける分割nは素数のそれぞれに対するN

2- SQRTが、リストにない要素までのすべての素数を、に追加のX *のSQRT（N）の時間複雑性を期待します結果は

3-リターン結果が

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] 

すべてOで

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 

テストを設定する設定しましたBig-Oで終わるソリューションのバリエーションは次のとおりです。sqrt（n）* list_size