Find the largest divisor N, which is less than sqrt (N)

Question

In fact, if N (possibly a very big one) is an even integer, I want to find N = F * R, where gcd (F, R) = 1, F> R and F are as small as possible (since I'll completely factorize F) . The heart of the problem is finding the greatest divisor R, where R <SQRT (N).

For example, N = 36 should give F = 9 and R = 4. Note that R is not necessarily prime or prime. Note that I DO NOT factorize N. The only restriction on F and R is that they are coprime.

This is my quick and naive version that works:

def factor_partial(N): for R in xrange(int(math.sqrt(N)),1,-1): if N%R == 0 and gcd(R,N/R) == 1: return N/R, R 

Another way I guess is to do this by finding the divisors in ascending order and removing any multiple non-divisors along the way. Sort of:

 def factor_partial(N): i = range(2, int(sqrt(N)) + 1) while i: if N % i[0] != 0: remove_multiples(i, i[0]) #without removing i[0] else: if gcd(i[0], N/i[0]) == 1: R = i[0] i.pop(0) #remove i[0] return N/R, R 

I think it will be slow and memory intensive, but perhaps if i could be an efficient generator instead. I did not use generators much.

Can the first version be improved? Is the second version viable (how do I do this)? Is there any other way that is better?

Search for answers in python, c or pseudo-code.

---

This is for a project for a class in number theory. I am running a primality test based on Pocklington . Although I need a factorization algorithm, we have not studied it, and I probably will not use a quadratic sieve that goes beyond the scope of my class. I am looking for specific help with this question.

Answer 1

Wikipedia has a good list of factoring algorithms: http://en.wikipedia.org/wiki/Integer_factorization#Factoring_algorithms

Your second approach effectively uses a sieve and has the good ability to quickly reduce the problem when N is a multiple of a majority number. The code can be improved by looping over primes, and not all possible divisors for 2..sqrt (n).

Alternatively, you can start with the primality test so that you know that N is composite before you do additional work.

Your note says that you do not factor N, but the problems are related. The search for F and R reduces to studying disjoint combinations of prime factors N.

In the case N==36 simple factorization of N is 2, 2, 3, 3 . Factors F and R must include all of these (so that F*R==N ) and there can be no overlap (so GCD(F,R)==1 ). So 4 and 9 appear immediately.

A more instructive example might be N==23256 . Its factorization is 2,2,2,3,3,17,19 . Since there can be no overlap between F and R, each main base can only go into one of two buckets (i.e. you get either all two or none of them). So we can group factors into 8,9,17,19 . To find R, we want the combination of these factors to be as large as possible, but below 152.49, the square root of 23256. Our options are {8}, {9}, {8.9}, {8.17}, {8, 19}. The largest of them is 8*19 , equal to 152. The corresponding F is 17*19 or 153.

The choices above are calculated as [choice for choice in powerset([8,9,17,19]) if prod(choice) < math.sqrt(N)] .

Thus, the entire program is largely reduced to the following:

 prime_factors = factorize(N) # [2,2,2,3,3,17,19] clusters = [p**e for p, e in collections.Counter(prime_factors).items()] # [8,9,17,19] R = max(prod(group) for group in powerset(clusters) if prod(group) < math.sqrt(N)) F = N // R 

A powerset search can be done faster by trimming the generation of sets when they exceed the square root of N.

Keep in mind that factorization is an expensive computer, and power plants grow very quickly, but probably much less than the original algorithm, which performs many divisions, starting from the square root of N and running down.

Answer 2

Could you get the primary factorization of N and then find the largest combination of products of all simple factors that is less than sqrt (N)?

For example, with 36 it will be established that simple factorization is 2 * 2 * 3 * 3. Then you can try all the different combinations of primes:

2 = 2
3 = 3
2 * 2 = 4
2 * 3 = 6
3 * 3 = 9
2 * 2 * 3 = 12
2 * 3 * 3 = 18
2 * 2 * 3 * 3 = 36

And you know that these are all factors from 36, so you will find the largest such that it is less than sqrt (36), which turns out to be 4.

However, I don’t see how this can be much faster than just making your first version, if you don’t already have an existing list of primes or simple factorizations, or some amazing simple factorization algorithm, or if you are doing all this with extremely large numbers .

But even then (back to the first version of nonsense) O (sqrt (n)) is a fairly fast runtime and requires only O (1) memory, so really the first option can be only one way. I don’t see how slow it will be, especially in C on a modern computer.

Answer 3

 def factor_partial(N): R = int(sqrt(float(N))) sieve = [1, 1] + [0] * (R-1) for i in xrange(2, R) : if sieve[i]==0 : j=i*i; while j<=R : sieve[j]=1 j = j + i primes = [i for i in xrange(R+1) if sieve[i]==0] saveN = N primepower_divisors = [] for i in primes : if N%i == 0 : term = 1 while N%i == 0 : term = term * i N = N / i primepower_divisors = primepower_divisors + [term] if N==1 : break largecoprime_divisors = [1] for i in primepower_divisors : for j in largecoprime_divisors : largecoprime_divisors = largecoprime_divisors + [i*j] F = min([i for i in largecoprime_divisors if i>R]) return F, saveN/F 

I used the sieve method to compute a list of primes (there are many optimizations possible when calculating a list of primes) We could use the fact that there will not be a prime p such that F% p == 0 and R% p == 0. since gcd (F, R) = 1