+- Qbasicnews.com (http://qbasicnews.com/newforum)
+-- Forum: QbasicNews.Com (http://qbasicnews.com/newforum/forum-3.html)
+--- Forum: Challenges (http://qbasicnews.com/newforum/forum-10.html)
+--- Thread: Prime factors in 25 lines or less (/thread-8202.html)
Prime factors in 25 lines or less - whodat - 10-10-2005
Quote:@ 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.
Prime factors in 25 lines or less - Rattrapmax6 - 10-10-2005
Your welcome... :wink:
Prime factors in 25 lines or less - Antoni Gual - 10-10-2005
Quote: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.
Prime factors in 25 lines or less - Quibbler - 10-10-2005
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 nPrime factors in 25 lines or less - Antoni Gual - 10-10-2005
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 subPrime factors in 25 lines or less - rpgfan3233 - 10-10-2005
Quote: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...I hope no round-off errors are experienced with those floating-point numbers. :roll:
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
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
Prime factors in 25 lines or less - Quibbler - 10-10-2005
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.
Prime factors in 25 lines or less - Antoni Gual - 10-11-2005
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.
Prime factors in 25 lines or less - Quibbler - 10-11-2005
Actually you can use long because the factors that need to be calculated never exceed long integer.
Prime factors in 25 lines or less - Antoni Gual - 10-11-2005
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...