Prime Factors

[sasha 99]

Hi Guys
I do these days an analytical research and i need some of help in this issue


I need to find a way to extract the prime factors of numbers with some special conditions .. Let's take an example to make it much more clear


IF i have an an integer number .. let's say 12682


I want to divide 12682 to a specific prime factors


let's say all prime factor which equal to or less than 5 .. the prime factors in this case consist of 2 , 3 , 5 .. any prime number more than 5 will be excluded


However , in some phases the result will not be divisible by 2 , 3 , 5
So this time we will use deduction in stead of division and we will determine a specific number to be used for all deduction calculations in next phases


we will use 7 for all deduction calculations and the process will continue on the same way for all next computational phases until we get to 1







12682 ÷ 2 = 6341
6341 - 7 = 6334

6334 ÷ 2 = 3167
3167 - 7 = 3160

3160 ÷ 2^3 = 395
415 ÷ 5 = 79
79 - 7 = 72

72 ÷ 2^3 = 9
9 ÷ 3^2 = 1

Note :: all result is INTEGER Number


Now , What is the best way to do these calculation and showing it in this sequence ?
so i can know how many time i use 2 , 3 and 5 in division
and how many time i use 7 in deduction


I am sure I will hear a brilliant answer from you , Don't disspoint me
Best Regard

 

[Eric W]

Interesting. Your example has at least one issue, the 415 should be 395. The other question I have is how do you decide to divide by a power of 2, or 3, or 5? Here's a version I came up with using formulas:

	A	B	C	D	E	F	G	H	I	J	K
Factors:
Max for GCD
/ 2 =
- 7 =	Deduct:
/ 2 =
- 7 =
/ 8 =
/ 5 =
- 7 =
/ 9 =
/ 8 =

<tbody>
[TD="align: center"]1[/TD]
[TD="align: right"]12682[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: right"]2[/TD]
[TD="align: right"]3[/TD]
[TD="align: right"]5[/TD]

[TD="align: center"]2[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: right"]8192[/TD]
[TD="align: right"]6561[/TD]
[TD="align: right"]3125[/TD]

[TD="align: center"]3[/TD]
[TD="align: right"][/TD]
[TD="align: right"]12682[/TD]

[TD="align: right"]6341[/TD]
[TD="align: right"][/TD]
[TD="align: right"]2[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]4[/TD]
[TD="align: right"][/TD]
[TD="align: right"]6341[/TD]

[TD="align: right"]6334[/TD]
[TD="align: right"][/TD]
[TD="align: right"]1[/TD]
[TD="align: right"][/TD]

[TD="align: right"]7[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]5[/TD]
[TD="align: right"][/TD]
[TD="align: right"]6334[/TD]

[TD="align: right"]3167[/TD]
[TD="align: right"][/TD]
[TD="align: right"]2[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]6[/TD]
[TD="align: right"][/TD]
[TD="align: right"]3167[/TD]

[TD="align: right"]3160[/TD]
[TD="align: right"][/TD]
[TD="align: right"]1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]7[/TD]
[TD="align: right"][/TD]
[TD="align: right"]3160[/TD]

[TD="align: right"]395[/TD]
[TD="align: right"][/TD]
[TD="align: right"]8[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]8[/TD]
[TD="align: right"][/TD]
[TD="align: right"]395[/TD]

[TD="align: right"]79[/TD]
[TD="align: right"][/TD]
[TD="align: right"]5[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]9[/TD]
[TD="align: right"][/TD]
[TD="align: right"]79[/TD]

[TD="align: right"]72[/TD]
[TD="align: right"][/TD]
[TD="align: right"]1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]10[/TD]
[TD="align: right"][/TD]
[TD="align: right"]72[/TD]

[TD="align: right"]8[/TD]
[TD="align: right"][/TD]
[TD="align: right"]9[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]11[/TD]
[TD="align: right"][/TD]
[TD="align: right"]8[/TD]

[TD="align: right"]1[/TD]
[TD="align: right"][/TD]
[TD="align: right"]8[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]12[/TD]
[TD="align: right"][/TD]
[TD="align: right"]1[/TD]

[TD="align: right"][/TD]

[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]13[/TD]
[TD="align: right"][/TD]

[TD="align: right"][/TD]

[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

</tbody>

Sheet2​

[TABLE="width: 85%"]
<tbody>[TR]
[TD]Worksheet Formulas[TABLE="width: 100%"]
<tbody>[TR]
[TH]Cell[/TH]
[TH="align: left"]Formula[/TH]
[/TR]
[TR]
[TH]F3[/TH]
[TD="align: left"]=IF(OR(B3=1,B3=""),"",MAX(GCD(B3,$I$2),GCD(B3,$J$2),GCD(B3,$K$2)))[/TD]
[/TR]
[TR]
[TH]B3[/TH]
[TD="align: left"]=A1[/TD]
[/TR]
[TR]
[TH]C3[/TH]
[TD="align: left"]=IF(OR(B3=1,B3=""),"",IF(F3>1,"/ "&F3,"- "&$I$4)& " =")[/TD]
[/TR]
[TR]
[TH]D3[/TH]
[TD="align: left"]=IF(C3="","",IF(LEFT(C3,1)="/",B3/F3,B3-$I$4))[/TD]
[/TR]
[TR]
[TH]B4[/TH]
[TD="align: left"]=IF(D3="","",D3)[/TD]
[/TR]
[TR]
[TH]I2[/TH]
[TD="align: left"]=I1^INT(LOG($A$1,I1))[/TD]
[/TR]
</tbody>[/TABLE]
[/TD]
[/TR]
</tbody>[/TABLE]



Put your number in A1, and your factors in I1:K1. Put the formulas in as shown, and drag down the columns as needed. This example matches your example until 72, where I divide by 9, and you divide by 8. My rule for selecting which factor to divide by is by finding the largest power of each factor that I can divide by evenly, then taking the largest value of that. If you have a different rule, let us know. According to the Commutative Property, I suppose it doesn't really matter.

 

[sasha 99]

All what i can say to you is .. you are a GENIUS

"If you have a different rule, let us know. According to the Commutative Property, I suppose it doesn't really matter."

No it does matter at all

I am happy with your answer but it is not a complete happy cuz the ending result is not like yours , although i follow your instruction but something went wrong
NOTE :: I use EXCEL 2007

Here's an screenshot

 

[Eric W]

It just looks like you have extra lines. If you want to insert an extra row between each calculation, that's fine, but you need to make sure that the formulas point to the right cells. The B4 formula should probably be in B5.

The easiest way I see to do this is to clear the B:F columns. Now enter the B3:F3 formulas as is. Enter the B4 formula in B5. Now paste the C3:F3 formulas to C5:F5. Now copy B5:F6, so you are copying a row of formulas and a blank row. Now select B7:F100 and paste the formulas, and you should be OK.

 

[sasha 99]

It just looks like you have extra lines. If you want to insert an extra row between each calculation, that's fine, but you need to make sure that the formulas point to the right cells. The B4 formula should probably be in B5.

The easiest way I see to do this is to clear the B:F columns. Now enter the B3:F3 formulas as is. Enter the B4 formula in B5. Now paste the C3:F3 formulas to C5:F5. Now copy B5:F6, so you are copying a row of formulas and a blank row. Now select B7:F100 and paste the formulas, and you should be OK.

i did literally what you said , but the result was not as expected
I just kindly ask you ( if possible ) to test the location of formula by yourself .. just to make sure that everything is in the right place
Here's the my screenshoot after your last instructions

 

[Eric W]

What formulas do you have in C5 and D5?

Here's the appearance of my sheet:

	A	B	C	D	E	F	G	H	I	J	K
Factors:
Max for GCD
/ 2 =
- 7 =	Deduct:
/ 2 =
- 7 =
/ 8 =
/ 5 =
- 7 =
/ 9 =
/ 8 =

<tbody>
[TD="align: center"]1[/TD]
[TD="align: right"]12682[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: right"]2[/TD]
[TD="align: right"]3[/TD]
[TD="align: right"]5[/TD]

[TD="align: center"]2[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: right"]8192[/TD]
[TD="align: right"]6561[/TD]
[TD="align: right"]3125[/TD]

[TD="align: center"]3[/TD]
[TD="align: right"][/TD]
[TD="align: right"]12682[/TD]

[TD="align: right"]6341[/TD]
[TD="align: right"][/TD]
[TD="align: right"]2[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]4[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]5[/TD]
[TD="align: right"][/TD]
[TD="align: right"]6341[/TD]

[TD="align: right"]6334[/TD]
[TD="align: right"][/TD]
[TD="align: right"]1[/TD]
[TD="align: right"][/TD]

[TD="align: right"]7[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]6[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]7[/TD]
[TD="align: right"][/TD]
[TD="align: right"]6334[/TD]

[TD="align: right"]3167[/TD]
[TD="align: right"][/TD]
[TD="align: right"]2[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]8[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]9[/TD]
[TD="align: right"][/TD]
[TD="align: right"]3167[/TD]

[TD="align: right"]3160[/TD]
[TD="align: right"][/TD]
[TD="align: right"]1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]10[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]11[/TD]
[TD="align: right"][/TD]
[TD="align: right"]3160[/TD]

[TD="align: right"]395[/TD]
[TD="align: right"][/TD]
[TD="align: right"]8[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]12[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]13[/TD]
[TD="align: right"][/TD]
[TD="align: right"]395[/TD]

[TD="align: right"]79[/TD]
[TD="align: right"][/TD]
[TD="align: right"]5[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]14[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]15[/TD]
[TD="align: right"][/TD]
[TD="align: right"]79[/TD]

[TD="align: right"]72[/TD]
[TD="align: right"][/TD]
[TD="align: right"]1[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]16[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]17[/TD]
[TD="align: right"][/TD]
[TD="align: right"]72[/TD]

[TD="align: right"]8[/TD]
[TD="align: right"][/TD]
[TD="align: right"]9[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]18[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]19[/TD]
[TD="align: right"][/TD]
[TD="align: right"]8[/TD]

[TD="align: right"]1[/TD]
[TD="align: right"][/TD]
[TD="align: right"]8[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]20[/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

[TD="align: center"]21[/TD]
[TD="align: right"][/TD]
[TD="align: right"]1[/TD]

[TD="align: right"][/TD]

[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]
[TD="align: right"][/TD]

</tbody>

Sheet2​

and the formulas for each cell:

	A	B	C	D	E	F	G	H	I	J	K
						Factors:
							Max for GCD	=I1^INT(LOG($A$1,I1))	=J1^INT(LOG($A$1,J1))	=K1^INT(LOG($A$1,K1))
	=A1	=IF(OR(B3=1,B3=""),"",IF(F3>1,"/ "&F3,"- "&$I$5)& " =")	=IF(C3="","",IF(LEFT(C3,1)="/",B3/F3,B3-$I$5))		=IF(OR(B3=1,B3=""),"",MAX(GCD(B3,$I$2),GCD(B3,$J$2),GCD(B3,$K$2)))
	=IF(D3="","",D3)	=IF(OR(B5=1,B5=""),"",IF(F5>1,"/ "&F5,"- "&$I$5)& " =")	=IF(C5="","",IF(LEFT(C5,1)="/",B5/F5,B5-$I$5))		=IF(OR(B5=1,B5=""),"",MAX(GCD(B5,$I$2),GCD(B5,$J$2),GCD(B5,$K$2)))		Deduct:
	=IF(D5="","",D5)	=IF(OR(B7=1,B7=""),"",IF(F7>1,"/ "&F7,"- "&$I$5)& " =")	=IF(C7="","",IF(LEFT(C7,1)="/",B7/F7,B7-$I$5))		=IF(OR(B7=1,B7=""),"",MAX(GCD(B7,$I$2),GCD(B7,$J$2),GCD(B7,$K$2)))
	=IF(D7="","",D7)	=IF(OR(B9=1,B9=""),"",IF(F9>1,"/ "&F9,"- "&$I$5)& " =")	=IF(C9="","",IF(LEFT(C9,1)="/",B9/F9,B9-$I$5))		=IF(OR(B9=1,B9=""),"",MAX(GCD(B9,$I$2),GCD(B9,$J$2),GCD(B9,$K$2)))
	=IF(D9="","",D9)	=IF(OR(B11=1,B11=""),"",IF(F11>1,"/ "&F11,"- "&$I$5)& " =")	=IF(C11="","",IF(LEFT(C11,1)="/",B11/F11,B11-$I$5))		=IF(OR(B11=1,B11=""),"",MAX(GCD(B11,$I$2),GCD(B11,$J$2),GCD(B11,$K$2)))
	=IF(D11="","",D11)	=IF(OR(B13=1,B13=""),"",IF(F13>1,"/ "&F13,"- "&$I$5)& " =")	=IF(C13="","",IF(LEFT(C13,1)="/",B13/F13,B13-$I$5))		=IF(OR(B13=1,B13=""),"",MAX(GCD(B13,$I$2),GCD(B13,$J$2),GCD(B13,$K$2)))
	=IF(D13="","",D13)	=IF(OR(B15=1,B15=""),"",IF(F15>1,"/ "&F15,"- "&$I$5)& " =")	=IF(C15="","",IF(LEFT(C15,1)="/",B15/F15,B15-$I$5))		=IF(OR(B15=1,B15=""),"",MAX(GCD(B15,$I$2),GCD(B15,$J$2),GCD(B15,$K$2)))
	=IF(D15="","",D15)	=IF(OR(B17=1,B17=""),"",IF(F17>1,"/ "&F17,"- "&$I$5)& " =")	=IF(C17="","",IF(LEFT(C17,1)="/",B17/F17,B17-$I$5))		=IF(OR(B17=1,B17=""),"",MAX(GCD(B17,$I$2),GCD(B17,$J$2),GCD(B17,$K$2)))
	=IF(D17="","",D17)	=IF(OR(B19=1,B19=""),"",IF(F19>1,"/ "&F19,"- "&$I$5)& " =")	=IF(C19="","",IF(LEFT(C19,1)="/",B19/F19,B19-$I$5))		=IF(OR(B19=1,B19=""),"",MAX(GCD(B19,$I$2),GCD(B19,$J$2),GCD(B19,$K$2)))
	=IF(D19="","",D19)

<tbody>
[TD="align: center"]1[/TD]
[TD="align: right"]12682[/TD]

[TD="align: right"]2[/TD]
[TD="align: right"]3[/TD]
[TD="align: right"]5[/TD]

[TD="align: center"]2[/TD]

[TD="align: center"]3[/TD]

[TD="align: center"]4[/TD]

[TD="align: center"]5[/TD]

[TD="align: right"]7[/TD]

[TD="align: center"]6[/TD]

[TD="align: center"]7[/TD]

[TD="align: center"]8[/TD]

[TD="align: center"]9[/TD]

[TD="align: center"]10[/TD]

[TD="align: center"]11[/TD]

[TD="align: center"]12[/TD]

[TD="align: center"]13[/TD]

[TD="align: center"]14[/TD]

[TD="align: center"]15[/TD]

[TD="align: center"]16[/TD]

[TD="align: center"]17[/TD]

[TD="align: center"]18[/TD]

[TD="align: center"]19[/TD]

[TD="align: center"]20[/TD]

[TD="align: center"]21[/TD]

</tbody>

Sheet4​

 

[sasha 99]

Finally it worked out
Thank you Eric from the depth of my heart , You made my day

 

[Eric W]

Glad you got it working!