Loading...
Searching...
No Matches
prime.cc File Reference
`#include <cmath>`
`#include "misc/prime.h"`
`#include "factory/cf_primes.h"`

Go to the source code of this file.

## Functions

static int | iiIsPrime0 (unsigned p)
int | IsPrime (int p)

## Function Documentation

## iiIsPrime0()

int iiIsPrime0 | ( | unsigned | p | ) |

static

Definition at line 12 of file prime.cc.

{
unsigned i,j=0 /*only to avoid compiler warnings*/;
if (p<=32749) // max. small prime in factory
{
int a=0;
int e=cf_getNumSmallPrimes()-1;
i=e/2;
do
{
j=cf_getSmallPrime(i);
if (p==j) 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);
}
unsigned end_i=cf_getNumSmallPrimes()-1;
unsigned end_p=(unsigned)sqrt((double)p);
restart:
for (i=0; i<end_i; i++)
{
j=cf_getSmallPrime(i);
if ((p%j) == 0)
{
if (p<=32751) return iiIsPrime0(p-2);
p-=2;
goto restart;
}
if (j > end_p) return p;
}
if (i>=end_i)
{
while(j<=end_p)
{
j+=2;
if ((p%j) == 0)
{
if (p<=32751) return iiIsPrime0(p-2);
p-=2;
goto restart;
}
}
}
return p;
}
i
int i
Definition cfEzgcd.cc:132
p
int p
Definition cfModGcd.cc:4086
cf_getNumSmallPrimes
int cf_getNumSmallPrimes()
Definition cf_primes.cc:34
cf_getSmallPrime
int cf_getSmallPrime(int i)
Definition cf_primes.cc:28
j
int j
Definition facHensel.cc:110
sqrt
gmp_float sqrt(const gmp_float &a)
Definition mpr_complex.cc:319
iiIsPrime0
static int iiIsPrime0(unsigned p)
Definition prime.cc:12

## IsPrime()

int IsPrime | ( | int | p | ) |

Definition at line 61 of file prime.cc.

{
if (p == 0) return 0;
else if (p == 1) return 1/*1*/;
else if ((p == 2)||(p==3)) return p;
else if (p < 0) return 2; //(iiIsPrime0((unsigned)(-p)));
else if ((p & 1)==0) return iiIsPrime0((unsigned)(p-1));
return iiIsPrime0((unsigned)(p));
}