kbruch/src/primenumber.cpp

   1 /***************************************************************************
   2                           primenumber.cpp  -  source code of class primenumber
   3                              -------------------
   4     begin                : Tue Nov 27 16:40:42 CET 2001
   5     copyright            : (C) 2001 by Sebastian Stein
   6     email                : seb.kde@hpfsc.de
   7  ***************************************************************************/
   8
   9 /***************************************************************************
  10  *                                                                         *
  11  *   This program is free software; you can redistribute it and/or modify  *
  12  *   it under the terms of the GNU General Public License as published by  *
  13  *   the Free Software Foundation; either version 2 of the License, or     *
  14  *   (at your option) any later version.                                   *
  15  *                                                                         *
  16  ***************************************************************************/
  17
  18 #include <kdebug.h>
  19 #include "primenumber.h"
  20
  21 /* ----- the global prime number vector ----- */
  22 UnsignedIntArray primenumber::prim_vector;
  23
  24 /* ----- public member functions ----- */
  25
  26 /*  constructor for class primenumber */
  27 primenumber::primenumber()
  28 {
  29         /* if the vector is empty, we will add the first 2 prime numbers */
  30         if (prim_vector.empty())
  31         {
  32 #ifdef DEBUG
  33                 kdDebug() << "prim_vector is still empty" << endl;
  34 #endif
  35
  36                 prim_vector.push_back(2);
  37                 prim_vector.push_back(3);
  38         }
  39         current_pos = prim_vector.begin();
  40 #ifdef DEBUG
  41         kdDebug() << "constructor primenumber" << endl;
  42 #endif
  43 }
  44
  45 /* destructor for class primenumber */
  46 primenumber::~primenumber()
  47 {
  48 #ifdef DEBUG
  49         kdDebug() << "destructor primenumber" << endl;
  50 #endif
  51 }
  52
  53 /* check, if the given number is a prime number;
  54  * return 0 if no, 1 if yes */
  55 short primenumber::isPrimeNumber(uint number)
  56 {
  57 #ifdef DEBUG
  58         kdDebug() << "primenumber::isPrimeNumber(" << number << ")" << endl;
  59 #endif
  60         /* 0 is not a prime number */
  61         if (number == 0)
  62                 return 0;
  63
  64         /* jump to the start of the vector */
  65         move_first();
  66
  67         /* check, if we can find a divisor */
  68         for (unsigned int dummy = get_first(); dummy < number; dummy = get_next())
  69         {
  70                 if ((number % dummy == 0) && (dummy != number))
  71                         return 0; // the number is not a prime number
  72
  73                 /* we found a prime number, because we only have to test the given
  74                  * number against all known prime numbers smaller square root of the
  75                  * number */
  76                 if (dummy * dummy > number)
  77                         return 1;
  78         }
  79
  80         return 1; // the given number is a prime number
  81 }
  82
  83 /* returns next prime number */
  84 unsigned int primenumber::get_next()
  85 {
  86         /* if we do not know the next number, we have to find it first */
  87         if (current_pos == prim_vector.end() ||
  88                 ++current_pos == prim_vector.end())
  89         {
  90                 /* we do not know the next prime number, so we have to find it */
  91                 find_next();
  92                 move_last();
  93                 return get_last(); /* return it */
  94         }
  95         else
  96         {
  97                 /* we know the next prime number, set the pointer on it */
  98                 return *current_pos; /* return it */
  99         }
 100 }
 101
 102 /* returns the first prime number of the vector */
 103 unsigned int primenumber::get_first() const
 104 {
 105         return *prim_vector.begin();
 106 }
 107
 108 /* returns the last prime number in the vector */
 109 unsigned int primenumber::get_last() const
 110 {
 111         return *(prim_vector.end() - 1);
 112 }
 113
 114 /* returns currently selected prime number */
 115 unsigned int primenumber::get_current() const
 116 {
 117         if (current_pos == prim_vector.end() + 1)
 118                 return get_last();
 119         return *current_pos;
 120 }
 121
 122 /* set current_pos to the first prime number */
 123 void primenumber::move_first()
 124 {
 125         current_pos = prim_vector.begin();
 126 }
 127
 128 /* set current_pos to the last prime number */
 129 void primenumber::move_last()
 130 {
 131         current_pos = prim_vector.end() - 1;
 132 }
 133
 134 /* move to the next prime number */
 135 void primenumber::move_forward()
 136 {
 137         /* if we are at the end of prim_vector, we have to find a new number */
 138         if (current_pos == prim_vector.end() ||
 139                 ++current_pos == prim_vector.end())
 140         {
 141                 find_next();
 142                 move_last();
 143         }
 144 }
 145
 146 /* move one prime number back */
 147 void primenumber::move_back()
 148 {
 149         /* current_pos must be at least pointing to the first element
 150          * of our vector after this function */
 151         if (current_pos != prim_vector.begin())
 152                 --current_pos;
 153 }
 154
 155 /* displays the whole prim_vector on stdout; just for debugging */
 156 void primenumber::display_all()
 157 {
 158         unsigned int dummy = 0; // count the numbers
 159
 160         /* looping through the complete vector */
 161         for (current_pos = prim_vector.begin(); current_pos != prim_vector.end();
 162                 current_pos++, dummy++)
 163                 kdDebug() << dummy << ": " << *current_pos << endl;
 164
 165         current_pos = prim_vector.end() - 1;
 166 }
 167
 168 /* ----- private member functions ----- */
 169
 170 /* finds next prime number and adds it to the vector */
 171 void primenumber::find_next()
 172 {
 173         /* our new prime number, must be bigger then the last one */
 174         unsigned int new_prim = *(prim_vector.end() - 1);
 175
 176         do
 177         {
 178                 /* new prime number must be bigger as biggest known one */
 179                 new_prim += 2;
 180                 /* loop as long as we find a divisor for the new number */
 181                 for (current_pos = prim_vector.begin(); current_pos != prim_vector.end();
 182                         current_pos++)
 183                         if ((new_prim % *current_pos == 0) || (new_prim < *current_pos))
 184                                 break;
 185
 186                 /* if we tried all known numbers and found no divisor, well,
 187                  * we are happy to have found a new prime number
 188                  *
 189                  * we found a prime number, because we only have to test the given
 190                  * number against all known prime numbers smaller square root of the
 191                  * number */
 192                 if ((current_pos == prim_vector.end())
 193                                 || (*current_pos * *current_pos > new_prim))
 194                         break;
 195         }
 196         while(1);
 197
 198         /* add the new prime number to the vector */
 199         prim_vector.push_back(new_prim);
 200
 201         current_pos = prim_vector.end() - 1;
 202 }