/[eiffelstudio]/trunk/eweasel/tests/incr071/primes.e
ViewVC logotype

Contents of /trunk/eweasel/tests/incr071/primes.e

Parent Directory Parent Directory | Revision Log Revision Log


Revision 65297 - (show annotations)
Thu Nov 30 20:22:33 2006 UTC (13 years ago) by manus
File size: 3948 byte(s)
Moved from trunk/Src/eweasel to trunk/eweasel so that a simple checkout of the source code is not penalized by the lenghty process of checking out all the tests of eweasel.
1 indexing
2
3 description:
4 "Prime number properties"
5
6 status: "See notice at end of class"
7 names: primes;
8 date: "$Date$"
9 revision: "$Revision$"
10
11 class PRIMES inherit
12
13 COUNTABLE_SEQUENCE [INTEGER]
14 rename
15 has as is_prime
16 redefine
17 is_prime
18 end
19
20 feature -- Access
21
22 Smallest_prime: INTEGER is 2
23
24 Smallest_odd_prime: INTEGER is 3
25
26 higher_prime (n: INTEGER): INTEGER is
27 -- Lowest prime greater than or equal to `n'
28 do
29 if n <= Smallest_prime then
30 Result := Smallest_prime
31 else
32 check
33 n > Smallest_prime
34 end
35 from
36 if n \\ Smallest_prime = 0 then
37 -- Make sure that `Result' is odd
38 Result := n + 1
39 else
40 Result := n
41 end
42 until
43 is_prime (Result)
44 loop
45 Result := Result + Smallest_prime
46 end
47 end
48 end
49
50 lower_prime (n: INTEGER): INTEGER is
51 -- Greatest prime lower than or equal to `n'
52 require
53 argument_big_enough: n >= Smallest_prime
54 do
55 if n = Smallest_prime then
56 Result := Smallest_prime
57 else
58 -- `n' > Smallest_prime
59 from
60 if n \\ Smallest_prime = 0 then
61 -- make sure that `Result' is odd
62 Result := n - 1
63 else
64 Result := n
65 end
66 until
67 is_prime (Result)
68 loop
69 Result := Result - Smallest_prime
70 end
71 end
72 end
73
74 all_lower_primes (n: INTEGER): ARRAY [BOOLEAN] is
75 -- Array of `n' boolean values, where the
76 -- value at index `i' is true if and only if
77 -- `i' is prime.
78 local
79 i, j: INTEGER
80 do
81 -- All odd numbers except 1 are candidates
82 from
83 create Result.make (1, n)
84 i := 3
85 until
86 i > n
87 loop
88 Result.put (True, i)
89 i := i + Smallest_prime
90 end
91 -- `Smallest_prime' is the lowest prime number
92 if n >= Smallest_prime then
93 Result.put (True, Smallest_prime)
94 end
95 -- Remove all multiples of primes
96 from
97 i := Smallest_odd_prime
98 until
99 i * i > n
100 loop
101 if Result.item (i) then
102 from
103 j := i * i
104 until
105 j > n
106 loop
107 Result.put (False, j)
108 j := j + Smallest_prime * i
109 end
110 end
111 i := i + Smallest_prime
112 end
113 end
114
115 is_prime (n: INTEGER): BOOLEAN is
116 -- Is `n' a prime number?
117 local
118 divisor: INTEGER
119 do
120 if n <= 1 then
121 Result := False
122 elseif n = Smallest_prime then
123 Result := True
124 elseif n \\ Smallest_prime /= 0 then
125 from
126 divisor := Smallest_odd_prime
127 until
128 (n \\ divisor = 0) or else (divisor * divisor >= n)
129 loop
130 divisor := divisor + Smallest_prime
131 end
132 if divisor * divisor > n then
133 Result := True
134 end
135 end
136 end
137
138 i_th (i: INTEGER): INTEGER is
139 -- The `i'-th prime number
140 local
141 candidates: ARRAY [BOOLEAN]
142 found: INTEGER
143 do
144 candidates := all_lower_primes (i * i)
145 from
146 Result := 2; found := 1
147 invariant
148 -- Between 1 and `Result' there are `found' primes.
149 variant
150 i * i - Result
151 until
152 found = i
153 loop
154 Result := Result + 1
155 if candidates.item (Result) then
156 found := found + 1
157 end
158 end
159 end
160
161 indexing
162
163 library: "[
164 EiffelBase: Library of reusable components for Eiffel.
165 ]"
166
167 status: "[
168 --| Copyright (c) 1993-2006 University of Southern California and contributors.
169 For ISE customers the original versions are an ISE product
170 covered by the ISE Eiffel license and support agreements.
171 ]"
172
173 license: "[
174 EiffelBase may now be used by anyone as FREE SOFTWARE to
175 develop any product, public-domain or commercial, without
176 payment to ISE, under the terms of the ISE Free Eiffel Library
177 License (IFELL) at http://eiffel.com/products/base/license.html.
178 ]"
179
180 source: "[
181 Interactive Software Engineering Inc.
182 ISE Building
183 360 Storke Road, Goleta, CA 93117 USA
184 Telephone 805-685-1006, Fax 805-685-6869
185 Electronic mail <info@eiffel.com>
186 Customer support http://support.eiffel.com
187 ]"
188
189 info: "[
190 For latest info see award-winning pages: http://eiffel.com
191 ]"
192
193 end -- class PRIMES
194
195
196

Properties

Name Value
svn:eol-style native
svn:keywords Author Date Id Revision

  ViewVC Help
Powered by ViewVC 1.1.23