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. Sigh... Any thoughts, one guy on the internetzzzz solved it using a wheel prime sieve, not sure what that is. Thanks anyways. |
|
|
I don't understand what you want. |
I'm just looking for some general thoughts. |
|
|
4199040000: 495 factors in 0 seconds. 864568320061: 4 factors in 0.051 seconds. 478585848547436: 24 factors in 0.902 seconds. 5454091843200000: 14256 factors in 3.207 seconds. 54540918432000000: 18144 factors in 10.441 seconds. |
ok then i would definitly use a while or for loop. and I found this website. http://www.mathwarehouse.com/arithmetic/numbers/prime-number/prime-factorization-calculator.php also what is the time limit exactly? |
How big are these numbers? And how slow is too slow? |
24 12 8 6 1 2 3 4 (5 is not a factor, and 6 is the last number on the top line) |
36 18 12 9 (6 is already written below) 1 2 3 4 6 |
|
|