Prime factors in 25 lines or less

[whodat]

@ Whodat: Go to your profile and check the "Always allow BBCode:", make sure that is selected to "Yes".... Then the BB code will work and you wont have to back it out... :wink:

Thanks. Did that and I think I'm getting the hang of it.

[Rattrapmax6]

Your welcome... :wink:

[Antoni Gual]

Nice, methinks you could probably create some sort of string with the values of the first X primes to speed it up too.. or something.

Aga: Probably calculating that primes would be slower than doing the tests, unless that primes were hardwired with the program.
Notice that removing the multiples of 3 and 2 avoids 2/3 of the tests (IIRC), further optimizations would give only minor gains.

[Quibbler]

Code:

DEFLNG N
INPUT "number to be factorized"; n
DIM a(22000) AS STRING * 1
FOR J = 2 TO 110
IF a(J) <> CHR$(0) GOTO 10
IST = J + J - 1
FOR i = J + IST TO 22000 STEP IST
a(i) = CHR$(1)
NEXT i
10 NEXT J
i = 1
WHILE n MOD 2 = 0
PRINT "2   ";
n = n \ 2
WEND
110 WHILE i < 22000
i = i + 1
IF a(i) = CHR$(0) AND n MOD (i + i - 1) = 0 THEN
PRINT i + i - 1;
jq = jq * (i + i - 1)
n = n \ (i + i - 1)
i = 1
END IF
WEND
IF n > 1 THEN PRINT n

[Antoni Gual]

I have enhanced my post by using DOUBLEs to be able to factorize values up to 5e15. By using ffix it declares 4999999999999997 prime in 12 seconds in my computer ..I hope it's really prime...

EDITED: It is. You can check your factorizations here http://www.alpertron.com.ar/ECM.HTM

Code:

declare sub ffix()
declare sub checkf(k#)

dim shared x#,C#
ffix
do
  print
   INPUT "enter a number to factorize[0 to end] : ", x#
   if x#<=0 or x#>5E15 then exit do
   t!=timer:c#=1
   PRINT "the prime factors are:";
   checkf(2#)
   checkf(3#)
   a#=2
   k# = 3 + a#
   WHILE K# <= sqr(x#)
     checkf(k#)
     k# = k# + a#
     a#=6#-a#
   WEND
   if x#>1 then print x#;:c#=c#*x#
   print: PRINT "Ended in ";timer-t!;" seconds. Product of all factors: "; C#
loop
sleep
sub checkf(k#)
do
  x1# = x# / k#
  if x1#-int(x1#)>1e-15 then exit do
  PRINT k#;
  C#=C#*K#
  x#=x1#
loop
end sub

[rpgfan3233]

I have enhanced my post by using DOUBLEs to be able to factorize values up to 5e15. By using ffix it declares 4999999999999997 prime in 12 seconds in my computer ..I hope it's really prime...

EDITED: It is. You can check your factorizations here http://www.alpertron.com.ar/ECM.HTM

Code:

declare sub ffix()
declare sub checkf(k#)

dim shared x#,C#
ffix
do
  print
   INPUT "enter a number to factorize[0 to end] : ", x#
   if x#<=0 or x#>5E15 then exit do
   t!=timer:c#=1
   PRINT "the prime factors are:";
   checkf(2#)
   checkf(3#)
   a#=2
   k# = 3 + a#
   WHILE K# <= sqr(x#)
     checkf(k#)
     k# = k# + a#
     a#=6#-a#
   WEND
   if x#>1 then print x#;:c#=c#*x#
   print: PRINT "Ended in ";timer-t!;" seconds. Product of all factors: "; C#
loop
sleep
sub checkf(k#)
do
  x1# = x# / k#
  if x1#-int(x1#)>1e-15 then exit do
  PRINT k#;
  C#=C#*K#
  x#=x1#
loop
end sub

I hope no round-off errors are experienced with those floating-point numbers. :roll:

[Quibbler]

You've got a fast computer there Antoni. On my computer it took 143 sec (with FFIX) and without it (FFIX) it still hasn't finished.
Is there the same problem (bug?) with integer arithmetic. I say this because double with FFIX seems to run faster than long integer.

[Antoni Gual]

A LONG will not allow you to factorize 4999999999999997. It should give you an overflow....And in modern computers, double can be faster than a long calculated in 16 bits mode.

There are no rounding errors I know of: the tests I ran gave the same result than Mr Alpert site. However I have not tested all integers from 1 to 1e15 using both methods If you find some wrong result, please let me know.

[Quibbler]

Actually you can use long because the factors that need to be calculated never exceed long integer.

[Antoni Gual]

You're right, but your way is slower:
If the number to factorize is double and the factors are long, factors must be converted to double every time they are operated or compared with the number. The results of the operations are double so they must be converted back if they are stored in a long...