File indexing completed on 2024-04-28 07:29:07
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 }