Submitted by chrisws on

__Title: First Factors
Description: __

Category: Mathematics

Copyright: MGA

Created: 10/19/14

GIST: https://gist.github.com/anonymous/3d14881f261cb5be0d3b

*'First Factors MGA.BAS 10/19/14 *

*'modified 10/24/14 with screen displays improvement a neat general code tip!*

*' for email to SmallBASIC crew*

*'I was challenged/inspired by the featured Primes.BAS code in SmallBASIC forum 10/18/14*

*'First Factors works from a different angle producing an array that is actually useful *

*'for finding more than just prime numbers. Use it to factor any number up to...*

*'topN, I left it at 1223 because that is the 200th prime found with Primes.BAS*

*'on my machine and system I get .002+ or .004+ secs for 200 primes but .02+ something with Primes.BAS*

*'of course I've gone up to 100,000 for TopN with .2+ secs results*

*'The algorithm is based on Sieve of Eratostheses, *

*'old as Greek Geometry with some prime number study added.*

*'Ha! looking up how to spell Sieve of Eratostheses I learn of Euler's Sieve (Wiki)*

*'n+1... there is always more that one can do, if one can do something!*

*'THANK YOU SmallBASIC crew and the Open Code Spirit - MGA*

*'*

*' This program code is a great first tool for Number Theory Study*

*' I think it's pretty good for teaching SmallBASIC as well*

*'*

option base 1

*'===================== topN =1223 for first 200 primes*

*'===================== topN =1000000 2.5+secs to load, 3.7+ to load and count*

topN=1223

testlimitN=sqr(topN)

dim ffA(topN+6)

*'In first FOR loop:*

*'you could go nuts performance wise and build patterns with 30 or 210 which are prime factorials*

*'here is just 6=2*3 which is an improvement on just 2 odds and evens. *

*'Prime factorials: 30=2*3*5 and 210=2*3*5*7... these create ever expanding and overlapping patterns*

tock=ticks

for i = 0 to topN step 6

ffA(i+1)=1:ffA(i+2)=2:ffA(i+3)=3:ffA(i+4)=2:ffA(i+5)=1:ffA(i+6)=2

next

ffa(2)=1:ffa(3)=1 *'fix first two primes*

for pcand=5 to testlimitN step 2

if ffA(pcand)=1 then

for i=pcand+pcand to topN step pcand

if ffA(i)=1 then ffA(i)=pcand : i=i+pcand *'booster shot .02 secs on 100,000*

next

fi

next

tic=ticks

?

print topN; " First Factors Array Complete in ";(tic-tock)/tickspersec;" secs."

?

pcount=0

for i =2 to topN

if ffA(i)=1 then pcount =pcount +1

next

tic =ticks

print "In first ";topN;" numbers there are ";pcount;" Primes."

?

print " In case a prime is not a prime until it is counted as one:"

? "It took "; (tic-tock)/tickspersec; " secs to load First Factor Array and count it*'s Primes."*

?

Print" press any "

?

pause

*'the following demo's a neat way to display tons of screens of data or file*

*'and stop it where you want, great general programming tip!*

cls

for i=2 to topN

if ffa(i)=1 then

print i,

count=count +1

if frac(count/10)=0 then print

if frac(count/200)=0 then

?:Input " ** enter s to stop display, just enter to continue **";s

if ucase(s)="S" then exit

cls

fi

fi

next

*' now let's use our array for something useful besides prime numbers*

label FactorNumber

?

? "Enter a number up to "+TopN+" to factor ( <2 to quit ) ";

input xn

if xn >= 2 and xn <=topN then

? xn; " factors are: ",

while ffA(xn)<>1

print ffa(xn),

xn=xn/ffa(xn)

wend

print xn

?

else

*'I have learned with SmallBASIC we need to say when we are done*

*'because in SmallBASIC we can go back and look inside our code while*

*'the program is running, its nice feature but can mess you up if you *

*'forget the program is still running *

?:? "That*'s all Folks!"*

END

fi

goto FactorNumber

*' now use this code to do your own number studies*