...

View Full Version : What is the algorithm to compute the factorisation of an integer?



laland
10-30-2006, 03:41 PM
Hi,
I need some ideas on how to compute the factorisation of a non-zero integer?
For example:
if the user input is 8, its factorisation is 1 * 2 * 2 * 2;
if the user input is -300, its factorisation is -1 * 2 * 2 * 3 * 5 * 5

Does anyone know?

Thanks

Philip M
10-30-2006, 04:34 PM
I have this in my library - I do not know where it came from.

<HTML>
<HEAD>
<title>Number Factorer</title>
<style>
<!--
SPAN#calcNotice { container: positioned; position: absolute; top: 150px; left: 200px;
z-index: 5; background-color: #c0c0c0; border: 5px outset; visibility: hidden }
-->
</style>
<SCRIPT>
<!--

function factor() {
origNum = parseInt( document.forms[0].toBeFactored.value );
numFac = origNum;
if ( isNaN( numFac ) || ( numFac <= 0 ) ) {
alert( "Please enter a non-zero positive integer." );
} else {
document.all.facNum.innerText = numFac;
document.all.calcNotice.style.visibility = "visible";
factorListHolder = "";
document.all.factorList.innerText = "";
PrimeFlag = true; while ( ( numFac % 2 == 0 ) && ( numFac != 2 ) ) {
PrimeFlag = false;
factorListHolder = factorListHolder + "2 ";
numFac = numFac / 2;
}
Test = 3;
maxTest = Math.sqrt( numFac );
while ( Test <= maxTest ) {
if ( numFac % Test == 0 ) {
PrimeFlag = false;
numFac = numFac / Test;
factorListHolder = factorListHolder + Test + " ";
} else {
Test = Test + 2;
}
}
if ( numFac != 1 ) {
if ( ( numFac != origNum ) && ( !PrimeFlag ) ) {
factorListHolder = factorListHolder + numFac;
}
}
if ( PrimeFlag ) {
document.all.factorList.innerText = "none besides 1 and itself.";
document.all.prevOutPuts.innerHTML = document.all.prevOutPuts.innerHTML + "Factors of " + origNum + " are none besides 1 and itself.<br>";
} else {
document.all.factorList.innerText = factorListHolder;
document.all.prevOutPuts.innerHTML = document.all.prevOutPuts.innerHTML + "Factors of " + origNum + " are " + factorListHolder + "<br>";
}
document.all.calcNotice.style.visibility = "hidden";
}
}

// -->
</SCRIPT>
</HEAD>
<BODY>

<FORM>
Factor <input type="text" id="toBeFactored"><button onclick="factor();">Go!</button>
</FORM>
<h1>Factorer</h1>
<p>Factors of <span id="facNum">44100</span> are <span id="factorList">2 2 3 3 5 5 7 7</span></p>

<h2>Previous Outputs</h2>
<span id="prevOutPuts"></span>

<span id=calcNotice><p>Calculating...</p></span>

</BODY>
</HTML>

VortexCortex
10-30-2006, 04:57 PM
Show us what you've got so far and we'll help you out.

P.S. the above script does not work in Netscape or FireFox.

VortexCortex
10-30-2006, 05:04 PM
Well, while we're pasting code examples...
Here's a script I wrote that returns an array of the factors so you can actually do something with them once the factoring is complete.


<html>
<head>
<title>Prime Factors</title>
<script type="text/javascript">
function getFactors(num){
var n; //Variable to store the current number.
var f = new Array(); //Array to hold the factors.
if(!isNaN(n = parseInt(num, 10))&&(n != 0)){ //Convert n into an integer and make sure num is a number and non zero.
f[f.length] = n / (n = Math.abs(n)); //Make first element either 1 or -1 and convert n to a positive number for faster factoring.
var i = 2; //Variable to hold current factor.
while(i < n){
if (n % i == 0){ //i is a factor of n
n /= i; //divide n by its factor.
f[f.length]=i; //store the factor.
i = 2; //start over at factor of 2.
} else if (i > 2) i+=2; //Avoid even numbers since 2 is the only even prime.
else i=3; //try 3 as a factor.
}
f[f.length]=n; //i now equals n, therefore n is a factor of num.
}
return f; //return the array of factors.
}
</script>
</head>
<body>
<h1>Prime Factors</h1>
Number to factor:<input id="num" size="10"><button onclick="alert('Prime Factors:\n'+getFactors(document.getElementById('num').value));">Get Factors</button>
</body>
</html>



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum