# How would you approach this puzzle? (Finding unique factors of a number only.)

I'm working on Interview Street's "Unfriendly Numbers" puzzle.

It goes like this:

Given an integer, and another list of integers, find the factors that are only unique to the given integer, and are not shared with the other list of integers.

So if set 1 (set Y) is (and n is the given number):

∃Y{z|n % z = 0}

Basically: There is a Y for every z, where z is a number where n % z is 0.

We want the set difference for Y minus the set that contains all the factors of the other list of numbers.

So how would you approach this?

Find the factors of integer n? All the factors of the other numbers and just weed out the non-unique factors?

Or would you only find the factors of n and just use them to divide the other numbers and weed out the non-unique ones?

Or is there a way to do it without factoring the number?

Thus far I've used Trial Division, Pollard's Rho, Brent's variation of Pollard's Rho and Fermat's method for factorization. I've also made use of the Lucas-Lehmer primality test and Euclids GCD.

But thus far, nothing, just a combination of wrong answers or exceeding the time limit. A known solution supposedly involves the wheel prime sieve but I'm unsure what that is.

Thanks anyways.

-
How fast were any of your previous solutions for factorization? Factorization of your integer N can be done in O(sqrt(N)) time. –  Felix Fung Apr 19 '12 at 2:41
Hmmm, well the Fermat way seemed to be the slowest (after trial division), but testing the numbers for primality seemed to slow it down too. If I didn't apply the primality test, but instead just used fermat's method and stopped the loop whenever a repeat factor was discovered, then all times came under the time limit. Only problem is, this might have stopped the loop prematurely, so all the answers were wrong. The Brent/Pollard methods seemed to be fast, but I think the problem is knowing when to stop factoring. If I apply the primality test to figure out when to stop, it slows down. –  James Yen Apr 19 '12 at 3:23
(continued) And maybe goes over the time limit, but I don't. I get wrong answers. Perhaps I should find the prime factorization and then somehow.... find all the normal factors from there? –  James Yen Apr 19 '12 at 3:25
How big are the numbers you are factoring? –  user448810 Apr 19 '12 at 12:45
Did you just copy the correct answer to your account on `Interview Street` and never come back to say thank you? –  kasavbere Apr 24 '12 at 23:34

Let your list be of size x and let the number be n. Then expect a time complexity of x* sqrt(n)

1-find all primes up to the sqrt of n

2- for each of the primes that divide n but no element in the list, add to result set

3- return result set

``````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)
}//if
return result;
}//uniqueFactors
``````

Test with

``````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]
``````

All other variations of a solution I run through still end up with Big-O : sqrt(n) * list_size

-
{"found_math": false, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}