Changeset cd22d1a in git

Timestamp:

Jan 31, 2003, 10:04:38 AM (21 years ago)

Author:

Hans Schönemann <hannes@…>

Branches:

(u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')

Children:

0b937c66fb6d3cee867a7255179563d6e5108b3b

Parents:

2eb3dbb39cecb0405a162b62f67738ea926e7e2e

Message:

*hannes: modified IsPrime: now also for p>32003, faster


git-svn-id: file:///usr/local/Singular/svn/trunk@6452 2c84dea3-7e68-4137-9b89-c4e89433aadc

File:

• Singular/ipshell.cc (modified) (3 diffs)

Singular/ipshell.cc

@@ -2 +2 @@
 *  Computer Algebra System SINGULAR     *
 ****************************************/
-/* $Id: ipshell.cc,v 1.78 2002-12-13 16:20:06 Singular Exp $ */
+/* $Id: ipshell.cc,v 1.79 2003-01-31 09:04:38 Singular Exp $ */
 /*
 * ABSTRACT:
@@ -11 +11 @@
 #include <string.h>
 #include <ctype.h>
+#include <math.h>
 
 #include "mod2.h"
@@ -578 +579 @@
   else if (p == 2)    return p;
   else if (p < 0)     return (-IsPrime(-p));
-  else if (p > 32002) return 32003; // without this line, max prime is 32749
   else if (!(p & 1)) return IsPrime(p-1);
 #ifdef HAVE_FACTORY
-  int a=0;
-  int e=cf_getNumSmallPrimes()-1;
-  i=e/2;
-  do
-  {
-    if (p==(j=cf_getSmallPrime(i))) return p;
-    if (p<j) e=i-1;
-    else     a=i+1;
-    i=a+(e-a)/2;
-  } while ( a<= e);
-  if (p>j) return j;
-  else     return cf_getSmallPrime(i-1);
+  else if (p<=32749) // max. small prime in factory
+  {
+    int a=0;
+    int e=cf_getNumSmallPrimes()-1;
+    i=e/2;
+    do
+    {
+      if (p==(j=cf_getSmallPrime(i))) return p;
+      if (p<j) e=i-1;
+      else     a=i+1;
+      i=a+(e-a)/2;
+    } while ( a<= e);
+    if (p>j) return j;
+    else     return cf_getSmallPrime(i-1);
+  }
+#endif
+#ifdef HAVE_FACTORY
+  int end_i=cf_getNumSmallPrimes()-1;
 #else
-  for (j=p/2+1,i=3; i<p; i+=2)
-  {
-    if ((p%i) == 0) return IsPrime(p-2);
-    if (j < i) return p;
+  int end_i=p/2;
+#endif  
+  int end_p=(int)sqrt((double)p);
+restart:
+  for (i=0; i<end_i; i++)
+  {
+#ifdef HAVE_FACTORY
+    j=cf_getSmallPrime(i);
+#else
+    if (i==0) j=2;
+    else j=2*i-1;
+#endif    
+    if ((p%j) == 0)
+    {
+    #ifdef HAVE_FACTORY
+      if (p<=32751) return IsPrime(p-2);
+    #endif  
+      p-=2;
+      goto restart;
+    }
+    if (j > end_p) return p;
   }
   return p;
-#endif
 }