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

/magnus/back_end/Group/include/PrimeNumbers.h

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 
00021 #ifndef _PRIMENUMBERS_H_
00022 #define _PRIMENUMBERS_H_
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
00043 class PrimeNumbers {
00044 public:
00045    PrimeNumbers() : currentNumber(2) {}
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 doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001