|
|
发表于 2023-9-25 13:11:34
|
显示全部楼层
- #include <iostream>#include <cmath>using namespace std;unsigned int MPow(unsigned int factor, unsigned int n){ unsigned int result = 1; for (unsigned int i = 0; i < n; ++i) result *= factor; return result;}// common list declaration and implementiontemplate <typename T>class SimpleList{private: struct SimpleListNode { explicit SimpleListNode (const T &obj, SimpleListNode *pt = 0) : data(obj), next(pt) { } T data; SimpleListNode *next; };public: class Iterator { public: explicit Iterator(SimpleListNode *pNode = 0) : node(pNode) { } T &operator *() { return node->data; } T *operator ->() const { return &(node->data); } Iterator &operator ++() { node = node->next; return *this; } friend bool operator == (const Iterator &it1, const Iterator &it2) { return it1.node == it2.node; } friend bool operator != (const Iterator &it1, const Iterator &it2) { return !(it1 == it2); } public: SimpleListNode *node; }; class ConstIterator { public: explicit ConstIterator(const SimpleListNode *pNode = 0) : node(pNode) { } const T &operator *() const { return node->data; } const T *operator ->() const { return &(node->data); } ConstIterator &operator ++() { node = node->next; return *this; } friend bool operator == (const ConstIterator &it1, const ConstIterator &it2) { return it1.node == it2.node; } friend bool operator != (const ConstIterator &it1, const ConstIterator &it2) { return !(it1 == it2); } public: const SimpleListNode *node; }; SimpleList() : head(0), tail(0) { } SimpleList(const SimpleList &lst) : head(0), tail(0) { append(lst); } ~SimpleList() { clear(); } SimpleList & operator = (const SimpleList &lst) { clear(); append(lst); } ConstIterator begin() const { return ConstIterator(head); } Iterator begin() { return Iterator(head); } ConstIterator end() const { return ConstIterator(0); } Iterator end() { return Iterator(0); } ConstIterator last() const { return ConstIterator(tail); } Iterator last() { return Iterator(tail); } void append(const SimpleList &lst) { for (SimpleListNode *p = lst.head; p; p = p->next) push_back(p->data); } void clear() { while(!empty()) { SimpleListNode *p = head->next; delete head; head = p; } } unsigned int size() const { unsigned int sz = 0; for (const SimpleListNode *p = head; p; p = p->next) ++sz; return sz; } bool empty() const { return head == 0; }; void push_front(const T &data) { head = new SimpleListNode(data, head); if(!tail) tail = head; } void push_back(const T &data) { if(tail) { tail->next = new SimpleListNode(data); tail = tail->next; } else { head = tail = new SimpleListNode(data); } } void pop_front() { SimpleListNode *tmp = head; if(head == tail) head = tail = 0; else head = head->next; delete tmp; } void pop_back() { if(head == tail) { delete head; head = tail = 0; } else { SimpleListNode *tmp; for(tmp = head; tmp->next != tail; tmp = tmp->next) ; delete tail; tail = tmp; tail->next = 0; } }private: SimpleListNode *head, *tail;};class MFactorCalulator{public: typedef SimpleList<unsigned int> MPrimeList; struct MFactor { MFactor(unsigned int fct, unsigned rep = 0) : factor(fct), repeat(rep) {} unsigned int factor; unsigned int repeat; }; typedef SimpleList<MFactor> MFactorList; struct MPerfectNumber { MPerfectNumber(unsigned int num, const MFactorList &factorList) : number(num), factors(factorList) {} unsigned int number; MFactorList factors; }; typedef SimpleList<MPerfectNumber> MPerfectNumberList;public: MFactorCalulator(unsigned int upper) : mUpper(upper) {} const MPrimeList &PrimeList() const { return mPrimeChain; } const MPerfectNumberList &PerfectNumberList() const { return mPerfectNumberChain; } void DoCalculate() { FindPrimes(mUpper); FindPerfectNumber(mUpper); }private: unsigned int mUpper; MPrimeList mPrimeChain; MPerfectNumberList mPerfectNumberChain; void FindPrimes(unsigned int upper) { mPrimeChain.clear(); mPrimeChain.push_back(2); mPrimeChain.push_back(3); for (unsigned int i = 5; i <= upper; i += 2) { for (MPrimeList::Iterator it = ++mPrimeChain.begin(); it != mPrimeChain.end() && (i % *it); ++it) { if (*it * *it > i) { mPrimeChain.push_back(i); break; } } } } void FindPerfectNumber(unsigned int upper) { for (unsigned int i = 2; i <= upper; ++i) CheckPerfectNumber(i); } bool CheckPerfectNumber(unsigned int number) { unsigned int quotient = number; MFactorList factor_list; for (MPrimeList::Iterator it = mPrimeChain.begin(); it != mPrimeChain.end(); ++it) { if (*it * *it > quotient) { MFactor factor1(quotient, 0); factor1.repeat = 1; factor_list.push_back(factor1); break; } MFactor factor(*it, 0); while (quotient % *it == 0) { ++factor.repeat; quotient /= *it; } if (factor.repeat > 0) factor_list.push_back(factor); } if (CalculateFactorSum(factor_list) == 2 * number) { mPerfectNumberChain.push_back(MPerfectNumber(number, factor_list)); return true; } return false; } unsigned int CalculateFactorSum(const MFactorList &chain) { unsigned int chainsize = chain.size(); MFactorList::ConstIterator *factor_arr = new MFactorList::ConstIterator[chainsize]; unsigned int* counter = new unsigned int[chainsize + 1]; // counter[chainsize] is to quit loop MFactorList::ConstIterator p = chain.begin(); for (unsigned int i = 0; i < chainsize; ++i, ++p) { factor_arr[i] = p; counter[i] = 0; } counter[chainsize] = 0; unsigned int sum = 0; while (!counter[chainsize]) // use the last element to quit loop { unsigned mix_product = 1; for (unsigned j = 0; j < chainsize; ++j) mix_product *= MPow(factor_arr[j]->factor, counter[j]); sum += mix_product; ++counter[0]; for (j = 0; (j < chainsize) && (counter[j] > factor_arr[j]->repeat); ++j) { counter[j] = 0; ++counter[j + 1]; } } delete []factor_arr; delete []counter; return sum; }};int main(){ cout << "Input max number: "; int upper; cin >> upper; MFactorCalulator calc(upper); calc.DoCalculate(); for (MFactorCalulator::MPerfectNumberList::ConstIterator it = calc.PerfectNumberList().begin(); it != calc.PerfectNumberList().end(); ++it) { cout << it->number << " = "; for (MFactorCalulator::MFactorList::ConstIterator itFactor = it->factors.begin(); (itFactor.node)->next != (it->factors.end()).node; ++itFactor) { cout << itFactor->factor << '^' << itFactor->repeat; cout << " * "; } cout << itFactor->factor << '^' << itFactor->repeat; cout << endl; } return 0;}
|
|
发表于 2023-9-25 13:08:40
