How do you design an algorithm to find factors of positive integer 12?

Answer 1

Step 1: Consider the problem, and solve it mentally.

Step 2: Examine how you solved it, and break that down into steps.

Step 3: Write out those steps, and plan code that follows them.

Step 4: Write the code.

Step 5: Debug the code.

If you didn't actually want to know how to design the algorithm, you may want to consider rephrasing your question.

For example, an algorithm to find all factors in a number:

Step 1: I would solve this by finding the smallest number greater than one that divides into the number in question, noting that number as one of it's factors, factoring that number out of it, and repeating it until the number has no factors other than one and itself.

Steps 2&3:

1. Take our given number.
2. Count in a loop from 2 up to the integer value of the number's square root (rounded down). Within that loop, if our number is divisible by our current count, break the loop.
3. If our count is less than or equal to the square root of our number, then:
   1. divide our number by the count
   2. note that count as one of the number's factors
   3. go to step 2, counting up from the number by which we just divided.

Step 4 (let's go with PHP):

function getFactors($val){

$factors = array();

$startVal = 2;

do{

$maxVal = intval(sqrt($val));

for($n = $startVal; $n <= $maxVal; $n++){

if(!($val % $n)){

break;

}

}

if($n <= $maxVal){

$factors[] = $n;

$repeat = true;

$startVal = $n;

}else{

$repeat = false;

}

}while($repeat);

return $factors;

}

?>

Step 5: I'll leave that to you.

Note that there will be more efficient ways of doing that. For example, that loop checks every number less than or equal to the square root of the number in question to see if it's a factor, but you only actually need to check the prime numbers in that range.