File indexing completed on 2022-12-06 18:52:33

0001 /*
0002     PrimeNumber.cpp  -  source code of class PrimeNumber
0003     SPDX-FileCopyrightText: 2001 Sebastian Stein <seb.kde@hpfsc.de>
0004 
0005     SPDX-License-Identifier: GPL-2.0-or-later
0006 */
0007 
0008 #include "PrimeNumber.h"
0009 
0010 #include <QDebug>
0011 
0012 
0013 /* ----- the global prime number vector ----- */
0014 UnsignedIntArray PrimeNumber::prim_vector;
0015 
0016 /* ----- public member functions ----- */
0017 
0018 /*  constructor for class primenumber */
0019 PrimeNumber::PrimeNumber()
0020 {
0021     /* if the vector is empty, we will add the first 2 prime numbers */
0022     if (prim_vector.empty()) {
0023 #ifdef DEBUG
0024         qDebug() << "prim_vector is still empty";
0025 #endif
0026 
0027         prim_vector.push_back(2);
0028         prim_vector.push_back(3);
0029     }
0030     current_pos = prim_vector.begin();
0031 #ifdef DEBUG
0032     qDebug() << "constructor primenumber";
0033 #endif
0034 }
0035 
0036 /* destructor for class primenumber */
0037 PrimeNumber::~PrimeNumber()
0038 {
0039 #ifdef DEBUG
0040     qDebug() << "destructor primenumber";
0041 #endif
0042 }
0043 
0044 /* check, if the given number is a prime number;
0045  * return 0 if no, 1 if yes */
0046 short PrimeNumber::isPrimeNumber(uint number)
0047 {
0048 #ifdef DEBUG
0049     qDebug() << "primenumber::isPrimeNumber(" << number << ")";
0050 #endif
0051     /* 0 is not a prime number */
0052     if (number == 0)
0053         return 0;
0054 
0055     /* jump to the start of the vector */
0056     move_first();
0057 
0058     /* check, if we can find a divisor */
0059     for (unsigned int dummy = get_first(); dummy < number; dummy = get_next()) {
0060         if ((number % dummy == 0) && (dummy != number))
0061             return 0; // the number is not a prime number
0062 
0063         /* we found a prime number, because we only have to test the given
0064          * number against all known prime numbers smaller square root of the
0065          * number */
0066         if (dummy * dummy > number)
0067             return 1;
0068     }
0069 
0070     return 1; // the given number is a prime number
0071 }
0072 
0073 /* returns next prime number */
0074 unsigned int PrimeNumber::get_next()
0075 {
0076     /* if we do not know the next number, we have to find it first */
0077     if (current_pos == prim_vector.end() ||
0078             ++current_pos == prim_vector.end()) {
0079         /* we do not know the next prime number, so we have to find it */
0080         find_next();
0081         move_last();
0082         return get_last(); /* return it */
0083     } else {
0084         /* we know the next prime number, set the pointer on it */
0085         return *current_pos; /* return it */
0086     }
0087 }
0088 
0089 /* returns the first prime number of the vector */
0090 unsigned int PrimeNumber::get_first() const
0091 {
0092     return *prim_vector.begin();
0093 }
0094 
0095 /* returns the last prime number in the vector */
0096 unsigned int PrimeNumber::get_last() const
0097 {
0098     return * (prim_vector.end() - 1);
0099 }
0100 
0101 /* returns currently selected prime number */
0102 unsigned int PrimeNumber::get_current() const
0103 {
0104     if (current_pos == prim_vector.end() + 1)
0105         return get_last();
0106     return *current_pos;
0107 }
0108 
0109 /* set current_pos to the first prime number */
0110 void PrimeNumber::move_first()
0111 {
0112     current_pos = prim_vector.begin();
0113 }
0114 
0115 /* set current_pos to the last prime number */
0116 void PrimeNumber::move_last()
0117 {
0118     current_pos = prim_vector.end() - 1;
0119 }
0120 
0121 /* move to the next prime number */
0122 void PrimeNumber::move_forward()
0123 {
0124     /* if we are at the end of prim_vector, we have to find a new number */
0125     if (current_pos == prim_vector.end() ||
0126             ++current_pos == prim_vector.end()) {
0127         find_next();
0128         move_last();
0129     }
0130 }
0131 
0132 /* move one prime number back */
0133 void PrimeNumber::move_back()
0134 {
0135     /* current_pos must be at least pointing to the first element
0136      * of our vector after this function */
0137     if (current_pos != prim_vector.begin())
0138         --current_pos;
0139 }
0140 
0141 /* displays the whole prim_vector on stdout; just for debugging */
0142 void PrimeNumber::display_all()
0143 {
0144     unsigned int dummy = 0; // count the numbers
0145 
0146     /* looping through the complete vector */
0147     for (current_pos = prim_vector.begin(); current_pos != prim_vector.end();
0148             current_pos++, dummy++)
0149         qDebug() << dummy << ": " << *current_pos;
0150 
0151     current_pos = prim_vector.end() - 1;
0152 }
0153 
0154 /* ----- private member functions ----- */
0155 
0156 /* finds next prime number and adds it to the vector */
0157 void PrimeNumber::find_next()
0158 {
0159     /* our new prime number, must be bigger than the last one */
0160     unsigned int new_prim = * (prim_vector.end() - 1);
0161 
0162     do {
0163         /* new prime number must be bigger as biggest known one */
0164         new_prim += 2;
0165         /* loop as long as we find a divisor for the new number */
0166         for (current_pos = prim_vector.begin(); current_pos != prim_vector.end();
0167                 ++current_pos)
0168             if ((new_prim % *current_pos == 0) || (new_prim < *current_pos))
0169                 break;
0170 
0171         /* if we tried all known numbers and found no divisor, well,
0172          * we are happy to have found a new prime number
0173          *
0174          * we found a prime number, because we only have to test the given
0175          * number against all known prime numbers smaller square root of the
0176          * number */
0177         if ((current_pos == prim_vector.end())
0178                 || (*current_pos * *current_pos > new_prim))
0179             break;
0180     } while (1);
0181 
0182     /* add the new prime number to the vector */
0183     prim_vector.push_back(new_prim);
0184 
0185     current_pos = prim_vector.end() - 1;
0186 }