(no subject)

[annathyst]

Actually, the only thing missing from the system is a procedure to (efficiently) produce a list of all the integer factors of an integer. Anyone want to take a stab at it?

Comments

well...

[price.livejournal.com]

prime factorization is actually incredibly bitchy. outside of "tricks" (its even, so 2 divides it), the only way to really derive the factors is to go through all ints from 1 to sqrt(n)

[slab]

here's a program that I wrote a few weeks ago for my TI-83, although it's probably a bit too inefficient for your requirements. And, yes, it probably can be done easier; 'twas my first calculator program. ;P

Input "NUMBER: ",A
For(B,2,A-1)
If ((int(A/B)*B)=A)
Then
Disp B
End
End

[techpimp.livejournal.com]

First, what system? And do you want ALL the factors or just the prime factorization? (Of course with the prime factorization you can find all the factors with a relatively simple algorithm.)

Second, the fastest algorithm for factoring numbers less than 110 digits is the Quadratic Sieve. (There are some derivatives that are faster but maybe too complicated for the 'system' you're targetting?) For over 110 digits it is the General Number Field Sieve (usually).

[techpimp.livejournal.com]

You only need to check up to 1/2 of A. A number greater than .5A can't be an integer factor because it can't be mulitplied by anything less than 2. (Unless I am reading your FOR statement wrong and you already do this?)

[pvx.livejournal.com]

pm(x,y)
Func
Local z,t
1->z
{}->t
While x<=y
If isPrime(x) Then
x->t[z]
z+1->z
EndIf
x+1->x
EndWhile
Return t
EndFunc

go go isPrime() go.

[annathyst]

How's quadratic sieve work?

[techpimp.livejournal.com]

It's...... complicated :)

Depending on what exactly you're trying to implement, it may be overkill. There are some intermediary things between the QS and simple trial division. Like the Continued Fraction Algorithm or good ol' Pollard's Monte Carlo alrogithm :)

What will work best depends on how easy it is to create arrays (sieves use big arrays, typically) and how fast division is, how fast modulo division is, etc...

What exactly are you targetting?

[lipid.livejournal.com]

half of A?
or sqrt(A)?