"Fossies" - the Fresh Open Source Software Archive

Member "mapm_4.9.5a/primenum.c" (21 Feb 2010, 6341 Bytes) of package /linux/misc/old/mapm-4.9.5a.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "primenum.c" see the Fossies "Dox" file reference documentation.

    1 
    2 /* 
    3  *  M_APM  -  primenum.c
    4  *
    5  *  Copyright (C) 1999 - 2007   Michael C. Ring
    6  *
    7  *  Permission to use, copy, and distribute this software and its
    8  *  documentation for any purpose with or without fee is hereby granted,
    9  *  provided that the above copyright notice appear in all copies and
   10  *  that both that copyright notice and this permission notice appear
   11  *  in supporting documentation.
   12  *
   13  *  Permission to modify the software is granted. Permission to distribute
   14  *  the modified code is granted. Modifications are to be distributed by
   15  *  using the file 'license.txt' as a template to modify the file header.
   16  *  'license.txt' is available in the official MAPM distribution.
   17  *
   18  *  This software is provided "as is" without express or implied warranty.
   19  */
   20 
   21 /*
   22  *      $Id: primenum.c,v 1.10 2007/12/03 02:05:01 mike Exp $
   23  *
   24  *      PRIME Number Generator using the MAPM Library
   25  *
   26  *  $Log: primenum.c,v $
   27  *  Revision 1.10  2007/12/03 02:05:01  mike
   28  *  update version
   29  *
   30  *  Revision 1.9  2007/12/03 02:00:42  mike
   31  *  Update license
   32  *
   33  *  Revision 1.8  2003/05/31 22:42:25  mike
   34  *  update version for display
   35  *
   36  *  Revision 1.7  2003/05/15 21:38:12  mike
   37  *  add MAPM version to output
   38  *
   39  *  Revision 1.6  2002/11/03 23:00:21  mike
   40  *  Updated function parameters to use the modern style
   41  *
   42  *  Revision 1.5  2002/02/12 20:52:16  mike
   43  *  add some needed comments and change the initial setups
   44  *
   45  *  Revision 1.4  2001/02/18 16:02:33  mike
   46  *  filter out multiples of 2,3,5, and 7
   47  *
   48  *  Revision 1.3  2001/02/15 23:11:13  mike
   49  *  slightly improved algorithm
   50  *
   51  *  Revision 1.2  1999/07/12 02:36:23  mike
   52  *  added more usage and added more comments
   53  *
   54  *  Revision 1.1  1999/07/12 02:31:23  mike
   55  *  Initial revision
   56  */
   57 
   58 #include <stdio.h>
   59 #include <stdlib.h>
   60 #include <string.h>
   61 #include <math.h>
   62 #include "m_apm.h"
   63 
   64 extern  int     is_number_prime(M_APM);
   65 extern  void    init_working_mapm(void);
   66 extern  void    free_working_mapm(void);
   67 
   68 #define FALSE 0
   69 #define TRUE 1
   70 
   71 char    buffer[2048];
   72 
   73 static  M_APM   M_limit, M_digit, M_quot, M_rem, M_tmp0, M_tmp1;
   74 
   75 
   76 /****************************************************************************/
   77 
   78 int main(int argc, char *argv[])
   79 {
   80 char     version_info[80];
   81 int      ct;
   82                 /* declare the M_APM variables ... */
   83 M_APM    aa_mapm;
   84 M_APM    bb_mapm;
   85 M_APM    cc_mapm;
   86 M_APM    dd_mapm;
   87 
   88 if (argc < 2)
   89   {
   90    m_apm_lib_short_version(version_info);
   91 
   92    fprintf(stdout,
   93       "Usage: primenum number\t\t\t[Version 1.4, MAPM Version %s]\n",
   94               version_info);
   95    fprintf(stdout,
   96       "       find the first 10 prime numbers starting with \'number\'\n");
   97 
   98    exit(4);
   99   }
  100                 /* now initialize the M_APM variables ... */
  101 aa_mapm = m_apm_init();
  102 bb_mapm = m_apm_init();
  103 cc_mapm = m_apm_init();
  104 dd_mapm = m_apm_init();
  105 
  106 init_working_mapm();
  107 
  108 m_apm_set_string(dd_mapm, argv[1]);
  109 
  110 /*
  111  *  if input < 3, set start point = 3
  112  */
  113 
  114 if (m_apm_compare(dd_mapm, MM_Three) == -1)
  115   {
  116    m_apm_copy(dd_mapm, MM_Three);
  117   }
  118 
  119 /*
  120  *  make sure we start with an odd integer
  121  */
  122 
  123 m_apm_integer_divide(aa_mapm, dd_mapm, MM_Two);
  124 m_apm_multiply(bb_mapm, MM_Two, aa_mapm);
  125 m_apm_add(aa_mapm, MM_One, bb_mapm);
  126 
  127 ct = 0;
  128 
  129 while (TRUE)
  130   {
  131    if (is_number_prime(aa_mapm))
  132      {
  133       m_apm_to_integer_string(buffer, aa_mapm);
  134       fprintf(stdout,"%s\n",buffer);
  135 
  136       if (++ct == 10)
  137         break;
  138      }
  139 
  140    m_apm_add(cc_mapm, MM_Two, aa_mapm);
  141    m_apm_copy(aa_mapm, cc_mapm);
  142   }
  143 
  144 free_working_mapm();
  145 
  146 m_apm_free(aa_mapm);
  147 m_apm_free(bb_mapm);
  148 m_apm_free(cc_mapm);
  149 m_apm_free(dd_mapm);
  150 
  151 m_apm_free_all_mem();
  152 
  153 exit(0);
  154 }
  155 
  156 /****************************************************************************/
  157 
  158 /*
  159  *      functions returns TRUE if the M_APM input number is prime
  160  *                        FALSE if it is not
  161  */
  162 int     is_number_prime(M_APM input)
  163 {
  164 int     ii, ret, index;
  165 char    sbuf[32];
  166 
  167 /*
  168  *      for reference:
  169  *
  170  *      table size of 2 to filter multiples of 2 and 3 
  171  *      table size of 8 to filter multiples of 2, 3 and 5
  172  *      table size of 480 to filter multiples of 2,3,5,7, and 11
  173  *
  174  *      this increment table will filter out all numbers
  175  *      that are multiples of 2,3,5 and 7.
  176  */
  177 
  178 static  char  incr_table[48] = {
  179         2, 4, 2, 4, 6, 2, 6, 4, 2, 4, 6, 6, 2, 6, 4, 2,
  180         6, 4, 6, 8, 4, 2, 4, 2, 4, 8, 6, 4, 6, 2, 4, 6,
  181         2, 6, 6, 4, 2, 4, 6, 2, 6, 4, 2, 4, 2, 10, 2, 10 };
  182    
  183 /* 
  184  *  since the real algorithm starts at 11 (to syncronize
  185  *  with the increment table), we will cheat for numbers < 10.
  186  */
  187 
  188 if (m_apm_compare(input, MM_Ten) <= 0)
  189   {
  190    m_apm_to_integer_string(sbuf, input);
  191    ii = atoi(sbuf);
  192 
  193    if (ii == 2 || ii == 3 || ii == 5 || ii == 7)
  194      return(TRUE);
  195    else
  196      return(FALSE);
  197   }
  198 
  199 ret   = FALSE;
  200 index = 0;
  201 
  202 /*
  203  *    see if the input number is a
  204  *    multiple of 3, 5, or 7.
  205  */
  206 
  207 m_apm_integer_div_rem(M_quot, M_rem, input, MM_Three);
  208 if (m_apm_sign(M_rem) == 0)               /* remainder == 0 */
  209   return(ret);
  210 
  211 m_apm_integer_div_rem(M_quot, M_rem, input, MM_Five);
  212 if (m_apm_sign(M_rem) == 0)
  213   return(ret);
  214 
  215 m_apm_set_long(M_digit, 7L);
  216 m_apm_integer_div_rem(M_quot, M_rem, input, M_digit);
  217 if (m_apm_sign(M_rem) == 0)
  218   return(ret);
  219 
  220 ii = m_apm_exponent(input) + 16;
  221 
  222 m_apm_sqrt(M_tmp1, ii, input);
  223 m_apm_add(M_limit, MM_Two, M_tmp1);
  224    
  225 m_apm_set_long(M_digit, 11L);              /* now start at '11' to check */
  226    
  227 while (TRUE)
  228   {
  229    if (m_apm_compare(M_digit, M_limit) >= 0)
  230      {
  231       ret = TRUE;
  232       break;
  233      }
  234    
  235    m_apm_integer_div_rem(M_quot, M_rem, input, M_digit);
  236    
  237    if (m_apm_sign(M_rem) == 0)         /* remainder == 0 */
  238      break;
  239    
  240    m_apm_set_long(M_tmp1, (long)incr_table[index]);
  241    m_apm_add(M_tmp0, M_digit, M_tmp1);
  242    m_apm_copy(M_digit, M_tmp0);
  243 
  244    if (++index == 48)
  245      index = 0;
  246   }
  247 
  248 return(ret);
  249 }
  250 
  251 /****************************************************************************/
  252 
  253 void    init_working_mapm()
  254 {
  255 M_limit = m_apm_init();
  256 M_digit = m_apm_init();
  257 M_quot  = m_apm_init();
  258 M_rem   = m_apm_init();
  259 M_tmp0  = m_apm_init();
  260 M_tmp1  = m_apm_init();
  261 }
  262 
  263 /****************************************************************************/
  264 
  265 void    free_working_mapm()
  266 {
  267 m_apm_free(M_limit);
  268 m_apm_free(M_digit);
  269 m_apm_free(M_quot);
  270 m_apm_free(M_rem);
  271 m_apm_free(M_tmp0);
  272 m_apm_free(M_tmp1);
  273 }
  274 
  275 /****************************************************************************/