Finding the factors of a number...

[VBproGGer]

Does anyone have an algorithm for finding the factors of a number?

[Guv]

Try searching this Forum. There was a Thread on this subject.

If you want to write a program to find all the prime factors of a given number, I would include a table of the first several hundred primes.

I have a program which runs on my HP calculator which has a table of the first 169 primes. Using it cuts the time down a fair amount.

My algorithm, first checks all the primes in that table. The last prime in the table is 1009, which is divisible by 6 with a remainder of one. This is important for the next part of the algorithm. Starting with such a prime, you add four and try that number as a divisor. Then you add two and try that one. You keep up this add four & add two scenario to find possible divisors. This cuts down the number of divisors to try.

Also, always take the square root of the number you are trying to factor. You never have to try any factor bigger than the square root.

[Megatron]

Try this.

// num is the number you want to list the factors of.
num = 12;

for( int x=num;x > 0 ; x-- )
{
    if( num % x == 0 )
    cout<< x << '\n';
}

[VBproGGer]

Um, that's C isn't it megatron, I want it in VB. NM tho, i found the thread.

[Guv]

Not beng familiar with C, I cannot really be sure ot what that code would do.

It cannot possibly find all the factors of a number. It is just too simple to be able to find all the factors.

It might find one factor if the the number is not a prime.

One of the traps in factoring programs is recognizing multiple factors. A number like 876,096 has the following factors.

13, 13, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2

If you merely want to discover that it is non prime, when you find that it is divisable by two, you know it is not prime and you are done.

If you want all the facxtors, you still have more work to do.

Right now, I anm very drunk & hope to get laid, so my mind is not focused on mathematics. I hope there are no typos, and that the avbove makes sense.

BTW: I just finsihed having a wondeful dinner at a gourmat restaurant. The salmon with provencial suace was magnificant, anf the macadama cheese cake was to die for. The Greek salsd was not bad.

The Blush Zinfandel, Cherry Kiafa, and Irish Cream liquor (in the coffee) was great.

BTW: Did you ever hear the sotroy about the football star on an atheletic scolarship who would pass his Engilsih course and be allowed to play, if he speeled one word correcdtly? The football coach objected to his being asked to spell coffee because it waqs a two syllable word. The English teacher compromised and siad he would pass if if got one letter right.

The football star spelled it: Kauphy.

[sql_lall]

All you have to do is something like:

(semi-Pseudo code, not real code):

num = number want to test

do until num = 1
label1:
loop lp1 from 2 to int(sqr(num))
if num mod lp1 = 0 then exit for (maybe: If num/lp1 = num\lp1 is faster)
next lp1
goto label1:
loop