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
|
/***************************************************************************
primenumber.cpp - source code of class primenumber
-------------------
begin : Tue Nov 27 16:40:42 CET 2001
copyright : (C) 2001 by Sebastian Stein
email : [email protected]
***************************************************************************/
/***************************************************************************
* *
* This program is free software; you can redistribute it and/or modify *
* it under the terms of the GNU General Public License as published by *
* the Free Software Foundation; either version 2 of the License, or *
* (at your option) any later version. *
* *
***************************************************************************/
#include <kdebug.h>
#include "primenumber.h"
/* ----- the global prime number vector ----- */
UnsignedIntArray primenumber::prim_vector;
/* ----- public member functions ----- */
/* constructor for class primenumber */
primenumber::primenumber()
{
/* if the vector is empty, we will add the first 2 prime numbers */
if (prim_vector.empty())
{
#ifdef DEBUG
kdDebug() << "prim_vector is still empty" << endl;
#endif
prim_vector.push_back(2);
prim_vector.push_back(3);
}
current_pos = prim_vector.begin();
#ifdef DEBUG
kdDebug() << "constructor primenumber" << endl;
#endif
}
/* destructor for class primenumber */
primenumber::~primenumber()
{
#ifdef DEBUG
kdDebug() << "destructor primenumber" << endl;
#endif
}
/* check, if the given number is a prime number;
* return 0 if no, 1 if yes */
short primenumber::isPrimeNumber(uint number)
{
#ifdef DEBUG
kdDebug() << "primenumber::isPrimeNumber(" << number << ")" << endl;
#endif
/* 0 is not a prime number */
if (number == 0)
return 0;
/* jump to the start of the vector */
move_first();
/* check, if we can find a divisor */
for (unsigned int dummy = get_first(); dummy < number; dummy = get_next())
{
if ((number % dummy == 0) && (dummy != number))
return 0; // the number is not a prime number
/* we found a prime number, because we only have to test the given
* number against all known prime numbers smaller square root of the
* number */
if (dummy * dummy > number)
return 1;
}
return 1; // the given number is a prime number
}
/* returns next prime number */
unsigned int primenumber::get_next()
{
/* if we do not know the next number, we have to find it first */
if (current_pos == prim_vector.end() ||
++current_pos == prim_vector.end())
{
/* we do not know the next prime number, so we have to find it */
find_next();
move_last();
return get_last(); /* return it */
}
else
{
/* we know the next prime number, set the pointer on it */
return *current_pos; /* return it */
}
}
/* returns the first prime number of the vector */
unsigned int primenumber::get_first() const
{
return *prim_vector.begin();
}
/* returns the last prime number in the vector */
unsigned int primenumber::get_last() const
{
return *(prim_vector.end() - 1);
}
/* returns currently selected prime number */
unsigned int primenumber::get_current() const
{
if (current_pos == prim_vector.end() + 1)
return get_last();
return *current_pos;
}
/* set current_pos to the first prime number */
void primenumber::move_first()
{
current_pos = prim_vector.begin();
}
/* set current_pos to the last prime number */
void primenumber::move_last()
{
current_pos = prim_vector.end() - 1;
}
/* move to the next prime number */
void primenumber::move_forward()
{
/* if we are at the end of prim_vector, we have to find a new number */
if (current_pos == prim_vector.end() ||
++current_pos == prim_vector.end())
{
find_next();
move_last();
}
}
/* move one prime number back */
void primenumber::move_back()
{
/* current_pos must be at least pointing to the first element
* of our vector after this function */
if (current_pos != prim_vector.begin())
--current_pos;
}
/* displays the whole prim_vector on stdout; just for debugging */
void primenumber::display_all()
{
unsigned int dummy = 0; // count the numbers
/* looping through the complete vector */
for (current_pos = prim_vector.begin(); current_pos != prim_vector.end();
current_pos++, dummy++)
kdDebug() << dummy << ": " << *current_pos << endl;
current_pos = prim_vector.end() - 1;
}
/* ----- private member functions ----- */
/* finds next prime number and adds it to the vector */
void primenumber::find_next()
{
/* our new prime number, must be bigger then the last one */
unsigned int new_prim = *(prim_vector.end() - 1);
do
{
/* new prime number must be bigger as biggest known one */
new_prim += 2;
/* loop as long as we find a divisor for the new number */
for (current_pos = prim_vector.begin(); current_pos != prim_vector.end();
current_pos++)
if ((new_prim % *current_pos == 0) || (new_prim < *current_pos))
break;
/* if we tried all known numbers and found no divisor, well,
* we are happy to have found a new prime number
*
* we found a prime number, because we only have to test the given
* number against all known prime numbers smaller square root of the
* number */
if ((current_pos == prim_vector.end())
|| (*current_pos * *current_pos > new_prim))
break;
}
while(1);
/* add the new prime number to the vector */
prim_vector.push_back(new_prim);
current_pos = prim_vector.end() - 1;
}
|
