Main Page   Class Hierarchy   Compound List   File List   Compound Members   File Members

Go to the documentation of this file.
```00001 /*
00002  *   \$Id:
00003  */
00004
00005 // Copyright (C) 1996 The New York Group Theory Cooperative
00006 // See magnus/doc/COPYRIGHT for the full notice.
00007
00008 // Contents: Definition of the PrimeNumbers and IntProblems classes
00009 //
00010 // Principal Author:  Alexey Myasnikov
00011 //
00012 // Status: in progress
00013 //
00014 // Usage:
00015 //
00016 // Special Notes:
00017 //
00018 // Revision History:
00019 //
00020
00023
00024 #include "Integer.h"
00025 #include "Vector.h"
00026 #include "DArray.h"
00027
00028 // IntProblems involces some methods to deal with Integers
00029 struct IntProblems
00030 {
00031   Integer gcdOfVector(const VectorOf<Integer>& vc)const;
00032   // Computes and returns the gcd of integers in
00033   // vector vc.
00034
00035   Integer powerOf(const Integer& o, const Integer& p)const;
00036   // Returns the power e if p^e = o, if not returns -1
00037
00038   void findCoeff(Integer p, Integer q, Integer& x, Integer& y, Integer mod)const;
00039   // Computes the coefficients x, y such that xp + yq = 1 (modulo mod)
00040 };
00041
00042 // Class with methods in which prime numbers are involved
00044 public:
00046    const Integer& current() const {
00047        return currentNumber;
00048    }
00049
00050    // Gives thee next prime number from current
00051    const Integer&  nextNumber(){
00052      while (true){
00053       currentNumber+=1;
00054       if (isPrime(currentNumber))
00055           return currentNumber;
00056       }
00057    }
00058
00059    // Sets the current number
00060    void setCurrent(const Integer& num){
00061        currentNumber = num;
00062    }
00063
00064    // True if number is prime
00065    bool isPrime(Integer num) const
00066      {
00067        for (int i=2;i<=sqrt(num);i++){
00068            if (num%i==0)
00069                 return false;
00070        }
00071        return true;
00072      }
00073
00074    // returns primary decomposition of num. First column - primes,
00075    // second their powers.
00076    DArray<Integer> getPrimeDecom(const Integer& num);
00077    // Prints primary decomposition of num in ostr. 2^3 + 3^2 + 5 ...
00078    void printPrimeDecom(ostream& ostr,const Integer& num);
00079 private:
00080    Integer currentNumber;
00081    // current prime number
00082 };
00083 #endif
```

Generated at Tue Jun 19 09:49:36 2001 for Magnus Classes by 1.2.6 written by Dimitri van Heesch, © 1997-2001