1.素数
当只需要判断某个数是否是素数的时候
bool isPrime(int x)
{
for(int i = 2; i * i <= n; i++)
{
if(x % i == 0)
return false;
}
return true;
}
当需要输出多个素数的时候:
bool notPrime[maxn];
int Prime[maxn];
int pnum = 0;
void findPrime( )
{
for(int i = 2; i < maxn; i++)
{
if(notPrime[i] == false)
{
Prime[pnum++] = i;
for(int j = i+i; j < maxn; j++)
notPrime[j] = true;
}
}
}//从前找没有访问过的数,将其倍数均设置为true,表示非素数
2.找最大公约数
int gcd(int a, int b)
{
if(b == 0)
return a;
else
return gcd(b, a % b);
}
3.分数的计算
struct fraction{
int up, down
};
fraction reduction(fraction a)
{
if(a.down < 0)
{
a.down = -a.down;
a.up = -a.up;
}
if(a.up == 0)
a.down == 1;
else
{
int d = a.up /= gcd(abs(a.up), abs(a.down));
a.up /= d;
a.down /= d;
}
return a;
}//简化是为了方便分数的加减
void print(fraction a)
{
if(a.down == 1)
printf("%d", a.up);
else if(abs(a.up) > abs(a.down))
printf("%d%d/%d", a.up/a.down, abs(a.up)%a.down, a.down);
else
printf("%d/%d", a.up, a.down);
}//分数以三种形式输出,整数,假分数,真分数的形式