In this section we will study checking a number for primality, how to find all divisors of a number up to $\sqrt{N}$ and factoring a number into prime numbers
What is a prime number?
A number is called prime if and only if has exactly two divisors: and the number itself.
How to find all divisors of a number ?
A naive solution is to iterate through all numbers from to and check divisibility.
Such a method works in . How to improve the code?
Note: if a number is a divisor of , then the number is also a divisor of , where .
The second important observation: , that is, at least one of the divisors in the pair is always not greater than .
This means that we can iterate only through numbers from to . If we find a divisor , then we also add to the set of divisors.
Thus, we can find all divisors of in .
Code example:
To test a number for primality, it is enough to count the number of its divisors.
If the number of divisors is two, then the number is prime; otherwise, it is composite.
Factorization is the decomposition of a number into prime factors.
The factorization algorithm is based on the same ideas as the primality test or finding divisors described above.
If a number has a prime divisor different from itself, then it does not exceed .
To factorize a number, you need to iterate through all numbers in the range from to and successively divide by the found divisors.
for (int i = 1; i <= N; i++) {
if (N % i == 0) {
...
}
}
vector<int> divisors;
for (int a = 1; a * a <= N; a++) {
if (N % a == 0) {
int b = N / a;
divisors.push_back(a);
if (a != b) {
divisors.push_back(b);
}
}
}
vector<int> factors;
for (int i = 2; i * i <= N; i++) {
while (N % i == 0) {
factors.push_back(i);
N /= i;
}
}
if (N > 1) {
factors.push_back(N);
}