《算法笔记》知识点总结

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);
}//分数以三种形式输出,整数,假分数,真分数的形式 
上一篇:奇怪的电梯


下一篇:2021-07-14