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); }//分数以三种形式输出,整数,假分数,真分数的形式