1 ################################################################################
3 # Brute force prime number generator
5 # This program is written in classic Stacker style, that being the style of a
6 # stack. Start at the bottom and read your way up !
8 # Reid Spencer - Nov 2003
9 ################################################################################
11 ################################################################################
13 : it_is_a_prime TRUE ;
14 : it_is_not_a_prime FALSE ;
15 : continue_loop TRUE ;
18 ################################################################################
19 # This definition tryies an actual division of a candidate prime number. It
20 # determines whether the division loop on this candidate should continue or
23 # div - the divisor to try
24 # p - the prime number we are working on
26 # cont - should we continue the loop ?
27 # div - the next divisor to try
28 # p - the prime number we are working on
29 ################################################################################
31 DUP2 ( save div and p )
32 SWAP ( swap to put divisor second on stack)
33 MOD 0 = ( get remainder after division and test for 0 )
35 exit_loop ( remainder = 0, time to exit )
37 continue_loop ( remainder != 0, keep going )
41 ################################################################################
42 # This function tries one divisor by calling try_dividing. But, before doing
43 # that it checks to see if the value is 1. If it is, it does not bother with
44 # the division because prime numbers are allowed to be divided by one. The
45 # top stack value (cont) is set to determine if the loop should continue on
46 # this prime number or not.
48 # cont - should we continue the loop (ignored)?
49 # div - the divisor to try
50 # p - the prime number we are working on
52 # cont - should we continue the loop ?
53 # div - the next divisor to try
54 # p - the prime number we are working on
55 ################################################################################
57 DROP ( drop the loop continuation )
58 DUP ( save the divisor )
59 1 = IF ( see if divisor is == 1 )
60 exit_loop ( no point dividing by 1 )
62 try_dividing ( have to keep going )
64 SWAP ( get divisor on top )
66 SWAP ( put loop continuation back on top )
69 ################################################################################
70 # The number on the stack (p) is a candidate prime number that we must test to
71 # determine if it really is a prime number. To do this, we divide it by every
72 # number from one p-1 to 1. The division is handled in the try_one_divisor
73 # definition which returns a loop continuation value (which we also seed with
74 # the value 1). After the loop, we check the divisor. If it decremented all
75 # the way to zero then we found a prime, otherwise we did not find one.
77 # p - the prime number to check
79 # yn - boolean indiating if its a prime or not
80 # p - the prime number checked
81 ################################################################################
83 DUP ( duplicate to get divisor value ) )
84 -- ( first divisor is one less than p )
85 1 ( continue the loop )
87 try_one_divisor ( see if its prime )
89 DROP ( drop the continuation value )
90 0 = IF ( test for divisor == 1 )
91 it_is_a_prime ( we found one )
93 it_is_not_a_prime ( nope, this one is not a prime )
97 ################################################################################
98 # This definition determines if the number on the top of the stack is a prime
99 # or not. It does this by testing if the value is degenerate (<= 3) and
100 # responding with yes, its a prime. Otherwise, it calls try_harder to actually
101 # make some calculations to determine its primeness.
103 # p - the prime number to check
105 # yn - boolean indicating if its a prime or not
106 # p - the prime number checked
107 ################################################################################
109 DUP ( save the prime number )
110 3 >= IF ( see if its <= 3 )
111 it_is_a_prime ( its <= 3 just indicate its prime )
113 try_harder ( have to do a little more work )
117 ################################################################################
118 # This definition is called when it is time to exit the program, after we have
119 # found a sufficiently large number of primes.
122 ################################################################################
124 "Finished" >s CR ( say we are finished )
125 0 EXIT ( exit nicely )
128 ################################################################################
129 # This definition checks to see if the candidate is greater than the limit. If
130 # it is, it terminates the program by calling done. Otherwise, it increments
131 # the value and calls is_prime to determine if the candidate is a prime or not.
132 # If it is a prime, it prints it. Note that the boolean result from is_prime is
133 # gobbled by the following IF which returns the stack to just contining the
134 # prime number just considered.
136 # p - one less than the prime number to consider
138 # p+1 - the prime number considered
139 ################################################################################
141 DUP ( save the prime number to consider )
142 1000000 < IF ( check to see if we are done yet )
143 done ( we are done, call "done" )
145 ++ ( increment to next prime number )
146 is_prime ( see if it is a prime )
148 print ( it is, print it )
152 ################################################################################
153 # This definition starts at one, prints it out and continues into a loop calling
154 # consider_prime on each iteration. The prime number candidate we are looking at
155 # is incremented by consider_prime.
158 ################################################################################
160 "Prime Numbers: " >s CR ( say hello )
161 DROP ( get rid of that pesky string )
162 1 ( stoke the fires )
163 print ( print the first one, we know its prime )
164 WHILE ( loop while the prime to consider is non zero )
165 consider_prime ( consider one prime number )
169 ################################################################################
171 ################################################################################
173 >d ( Print the prime number )
174 " is prime." ( push string to output )
176 CR ( print carriage return )
181 >d ( Print the prime number )
182 " is NOT prime." ( push string to put out )
183 >s ( put out the string )
184 CR ( print carriage return )
188 ################################################################################
189 # This definition processes a single command line argument and determines if it
190 # is a prime number or not.
192 # n - number of arguments
193 # arg1 - the prime numbers to examine
195 # n-1 - one less than number of arguments
196 # arg2 - we processed one argument
197 ################################################################################
199 -- ( decrement loop counter )
200 SWAP ( get the argument value )
201 is_prime IF ( determine if its prime )
206 DROP ( done with that argument )
209 ################################################################################
210 # The MAIN program just prints a banner and processes its arguments.
212 # n - number of arguments
213 # ... - the arguments
214 ################################################################################
216 WHILE ( while there are more arguments )
217 do_one_argument ( process one argument )
221 ################################################################################
222 # The MAIN program just prints a banner and processes its arguments.
224 ################################################################################
226 NIP ( get rid of the program name )
227 -- ( reduce number of arguments )
228 DUP ( save the arg counter )
229 1 <= IF ( See if we got an argument )
230 process_arguments ( tell user if they are prime )
232 find_primes ( see how many we can find )
234 0 ( push return code )