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