# Number Theory - broyda/cp-lib GitHub Wiki

# Why we prefer a check such as i*i <= n instead of i <= sqrt(n)?

Because we incur an extra log(n) cost when performing a sqrt function. Using the former variant means no cost at all.

# Global versus method local declaration of an array

In a method local array, the max size of an array is less than what could have been defined globally.

# Problem solving technique

For problems that involves factors etc. try out creative ways to store meta data in the sieve array itself. For example,

- Sieve array can store number of times a prime say 7 is multiplied for a given large number
**n**during the precomputation step. Refer L4 of Str lecture - the last problem discussed. - Store backpointers for all numbers 1 through n as to which prime number was used to mark this number as a composite. For this the array need to be initialized with the numbers themselves (e.g. a[5] = 5, a[6] = 6 and so on because doing so with also cause the primes to record the fact that they themselves are their factors). Refer L4 of Str lecture 25:00.
- Fact: For a given number
**n**, primes <=**sqrt(n)**are enough to generate all prime factors. For example, for 57 (3 * 19), 3 is enough to generate the remaining prime factors.

# Modulus function snippets

```
#define ll long long int
int mod = 1e9 + 7;
inline ll add(ll a, ll b) {
ll num = a + b;
if (num >= mod) {
num -= mod;
} else if (num < 0) {
num += mod;
}
return num;
}
inline ll sub(int a, int b) {
ll num = a - b;
if (num < 0) {
num += mod;
}
else if (num >= mod) {
num -= mod;
}
return num;
}
inline int mul(int a, int b) {
return (int) ((long long) a * b % mod);
}
inline int power(int a, long long b) {
int res = 1;
while (b > 0) {
if (b & 1) {
res = mul(res, a);
}
a = mul(a, a);
b >>= 1;
}
return res;
}
inline int inv(int a) {
a %= mod;
if (a < 0) a += mod;
int b = mod, u = 0, v = 1;
while (a) {
int t = b / a;
b -= t * a; swap(a, b);
u -= t * v; swap(u, v);
}
assert(b == 1);
if (u < 0) u += mod;
return u;
}
int fact[N];
void pre() {
fact[0] = 1;
for(int i = 1; i < N; i++)
fact[i] = mul(fact[i - 1], i);
return;
}
```

# Sieve of Eratothenes

```
int n = 200;
bool prime[201];
void SieveOfEratosthenes(int n)
{
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= n; p++) {
if (prime[p]) {
for (int i = p * p; i <= n; i += p) {
prime[i] = false;
}
}
}
/*for (int p = 2; p <= n; p++) {
if (prime[p]) {
cout << p << " ";
}
}*/
}
```