prime.hpp

浮点数基本运算 浮点数的基本运算主要有四则运算、符号处理、大小比较

// Prime implementation -*- C++ -*-

// Copyright (C) 2005 Ben T. Bear
//
// This file is part of the BTB's Template<Integer> Library.  This
// library is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

#ifndef __bt2il_prime_hpp
#define __bt2il_prime_hpp

namespace btil
{
  template <int n>
  struct prime;

  template <int p>
  struct is_prime;
  
  template <int p>
  struct upper_prime;


  template <>
  struct prime<0>
  {
    static const int value = 2;
    
    prime (int a[])
    {
      a[0] = 2;
    }
  };
  
  template <>
  struct prime<1>
  {
    static const int value = 3;
    prime (int a[])
    {
      a[0] = 2;
      a[1] = 3;
    }
  };

  template <>
  struct prime<2>
  {
    static const int value = 5;
    prime (int a[])
    {
      a[0] = 2;
      a[1] = 3;
      a[2] = 5;
    }
  };

  template <int n, int p>
  struct __next_prime;
  
  template <int n>
  struct prime: public prime<n-1>
  {
    static const int __p1 = prime<n-1>::value+2;
    static const int __p2 = (__p1 % 3) ? __p1 : __p1 + 2;
    static const int value = __next_prime<n-1, __p2>::value;
					  //prime<n-1>::value+2>::value;
    prime (int a[])
      : prime<n-1>(a)
    {
      a[n] = value;
      //(prime<n-1>(a));
    }
  };
  
  template <int n, int p>
  struct __test_n_prime;
  
  template <bool b, int n, int p>
  struct __next_prime_bool;

  template <int n, int p>
  struct __next_prime
  {
    static const int value = __next_prime_bool<__test_n_prime<n, p>::value,
					       n, p>::value;
  };
  
  template <int n, int p>
  struct __next_prime_bool<true, n, p>
  {
    static const int value = p;
  };
  
  template <int n, int p>
  struct __next_prime_bool<false, n, p>
  {
    static const int __p1 = p + 2;
    static const int __p2 = (__p1 % 3) ? __p1 : __p1+2;
    static const int value = __next_prime<n, __p2>::value;
  };
  
  template <int n, int p>
  struct __test_n_prime
  {
    static const bool value = (__test_n_prime<n-1, p>::value
			       && (p % prime<n>::value != 0));
  };
  
  template <int p>
  struct __test_n_prime<2, p>
  {
    static const bool value = (p % 5 != 0);//prime<1>::value != 0;
  };
  
  template <int n>
  void
  prime_array (int a[])
  {
    prime<n-1> t(a);
  }


  template <int n, int p>
  struct __is_n_prime;

  template <int p>
  struct is_prime
  {
    static const bool value = __is_n_prime<0, p>::value;
  };

  // lem: p 'Less than or 'Equal prime<N>, or p 'Mod prime<N> == 0
  template <bool c, int n, int p>
  struct __is_lem_n_prime;

  template <int n, int p>
  struct __is_n_prime
  {
    static const bool next = ((p <= prime<n>::value)
			      || (p % prime<n>::value == 0));
    static const bool value = __is_lem_n_prime<next, n, p>::value;
  };

  template <int n, int p>
  struct __is_lem_n_prime<true, n, p>
  {
    static const bool value = (p == prime<n>::value);
  };

  template <int n, int p>
  struct __is_lem_n_prime<false, n, p>
  {
    static const bool value = __is_n_prime<n+1, p>::value;
  };


  template <int n, int p>
  struct __upper_n_prime;
  
  template <int p>
  struct upper_prime
  {
    static const int value = __upper_n_prime<0, p>::value;
  };

  template <bool le, int n, int p>
  struct __next_upper_n_prime;

  template <int n, int p>
  struct __upper_n_prime
  {
    static const int le = (p <= prime<n>::value);
    static const int value = __next_upper_n_prime<le, n, p>::value;
  };

  template <int n, int p>
  struct __next_upper_n_prime<true, n, p>
  {
    static const int value = prime<n>::value;
  };

  template <int n, int p>
  struct __next_upper_n_prime<false, n, p>
  {
    static const int value = __upper_n_prime<n+1, p>::value;
  };
}

#endif