Factorising Algorithm: Solving AC=R

[2^Oscar]

Hey guys,

Very quick question. Can anyone recommend an algorithm for factorising a number (no more than 10,000,000) which will factorise a number into two smaller numbers both of which fall within predetermined limits? I'm trying to find a variety of solutions to the problem AC=R where R is a 6 digit number.

Cheers,
Oscar

 

[rcgldr]

no more than 10,000,000 ... R is 6 digit number

In this case the max value of R is 999,999. The maximum possible prime factor is

999999^1/2 < 1000

You'd need a table of all primes from 2 to the largest prime number < 1000. Then factor the number into all it's prime components, then create a list of all possible pairs of products of these prime factors AC = R. For example:

R = 48600 = 2³ x 3⁵ x 5²

A = 2^ (i = {0, 1, 2, 3}) x 3^(j = {0, 1, 2, 3, 4, 5}) x 5^(k = {0, 1, 2})
C = 2^(3-i) x 3^(5-j) x 5^(2-k)

You may want to drop the first case {i, j, k} = {0,0,0} = 1 x 48600 and the last case {i, j, k} = {3, 5, 2} = 48600 x 1.

 

[CRGreathouse]

For numbers that small, trial division is the only sensible algorithm (as Jeff suggests). Make a list of the first 168 (or 446*) primes and check for divisibility.

* For a limit of 10^6 and 10^7, respectively; you weren't entirely clear on this point.

 

[2^Oscar]

Hi,

I'm sorry about my lack of clarity I'll try to explain my problem in more detail. I have a ratio of this form:

R=BD/AC
Where R is a six digit decimal and B, D, A and C are integers between 20 and 81 inclusive.

What I'm trying to do is write an algorithm that will approximate values for A, B, C and D. My idea is to set AC as 1000000 and BD as 1000000R and then cancel the fraction down as far as I can with integers on top and bottom. Once I've done this I'm going to keep dividing by two until both AC and BD are between 20² and 81² (the maximum values they can be) then round to the nearest whole number for them both respectively. Once I've done this, I want to apply a factorising algorithm that will yield results for A and C and then B and D, giving me approximate values for them that give the best value of R I can.

Again I apologise for the lack of clarity, I am an A-level student and my dealings with both computing and actually writing algorithms is very limited so I have very little experience with this kind of thing!Thank you for the quick replies,
Oscar

 

[rcgldr]

There are only 22 prime numbers < 81.

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79

Every number from 1 to 81 is the product of some combination of numbers in this list:

1 2 2 2 2 2 2 3 3 3 3 5 5 7 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79

Note that R x AC = BD.

You could go through the list of primes testing for modulo with R and BD or AC and BD, dividing by that prime when the modulo is zero. Keeping track of the factors as you find them until you've gone through all 22 prime numbers.

For example if ((R%2 == 0) && (BD%2 == 0), then divide both by 2, and append 2 to the list of prime factors for R and BD.
Repeat the same process for AC and BD.

Note the list of factors for R and AC could each be 20 long (2^20 > 1,000,000), and 40 long for BD (2^40 > 10^12).

Also if the maximum value for A, B, C, and D is 81, then the maximum value for R = (81x81) / (1x1) = 6561, not a 6 digit number, unless you mean R is not an integer, but instead a floating (or fixed) point number.

If the range of A, B, C, D is limited to 20 => 81, then there are 62^4 = 14776336 possible combinations of A, B, C, D, small enough to brute force try all combinations if this is being done on a PC, and the time factor isn't critical. You could also generate a table with 14776336 entries on a PC, then sort the table, then remove any duplicate values (AC/BD), if you had enough ram, say 6GB on a PC.