PrevNext
Rare
 0/5

Divisibility

Authors: Darren Yao, Michael Cao, Andi Qu

Using the information that one integer evenly divides another.

If you've never encountered any number theory before, AoPS is a good place to start.

Resources
AoPSpractice problems, set focus to number theory!
AoPSgood book

Resources

Prime Factorization

Focus Problem – read through this problem before continuing!

A positive integer is called a divisor or a factor of a non-negative integer if is divisible by , which means that there exists some integer such that . An integer is prime if its only divisors are and . Integers greater than that are not prime are composite.

Every positive integer has a unique prime factorization: a way of decomposing it into a product of primes, as follows:

where the are distinct primes and the are positive integers.

Now, we will discuss how to find the prime factorization of any positive integer.

C++

vector<int> factor(int n) {
vector<int> ret;
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
ret.push_back(i);
n /= i;
}
}
if (n > 1) ret.push_back(n);
return ret;
}

Java

ArrayList<Integer> factor(int n) {
ArrayList<Integer> factors = new ArrayList<>();
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
factors.add(i);
n /= i;
}
}
if (n > 1) factors.add(n);
return factors;
}

Python

def factor(n):
ret = []
i = 2
while i * i <= n:
while n % i == 0:
ret.append(i)
n //= i
i += 1
if n > 1:
ret.append(n)
return ret

This algorithm runs in time, because the for loop checks divisibility for at most values. Even though there is a while loop inside the for loop, dividing by quickly reduces the value of , which means that the outer for loop runs less iterations, which actually speeds up the code.

Let's look at an example of how this algorithm works, for .

Example

At this point, the for loop terminates, because is already 3 which is greater than . In the last step, we add to the list of factors , because it otherwise won't be added, for a final prime factorization of .

Solution - Counting Divisors

The most straightforward solution is just to do what the problem asks us to do - for each , find the number of divisors of in time.

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
while (n--) {
int x, ans = 0;

Java

import java.io.*;
import java.util.*;
public class Main {
static int solve(int n) {
int divisors = 0;
for (int i = 1; i * i <= n; i++) {
if (n % i == 0) {
if (i * i == n) divisors++;
else divisors += 2;

This solution runs in time, which is just fast enough to get AC. However, we can actually speed this up to get an solution!

First, let's discuss an important property of the prime factorization. Consider:

Then the number of divisors of is simply .

Why is this true? The exponent of in any divisor of must be in the range and each different exponent results in a different set of divisors, so each contributes to the product.

can have distinct prime factors, so if we can find the prime factorization of efficiently, we can answer queries in time instead of the previous time.

Here's how we find the prime factorization of in time with preprocessing:

  • For each , find any prime number that divides .
    • We can use the Sieve of Eratosthenes to find this efficiently.
  • For each , we can then find the prime factorization by repeatedly dividing by a prime number that divides until .

Alternatively, we can slightly modify the the prime factorization code above.

C++

#include <bits/stdc++.h>
using namespace std;
int max_div[1000001];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
for (int i = 2; i <= 1000000; i++) {
if (!max_div[i]) {

Java

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

make java code consistent w/ C++ code ...

import java.io.*;
import java.util.*;
public class Main {
static int solve(int n) {
int divisors = 1;
for (int i = 2; i * i <= n; i++) {
int ct = 0;
while (n % i == 0) {
ct++;
Optional

Apply the linear sieve.

GCD & LCM

GCD

The greatest common divisor (GCD) of two integers and is the largest integer that is a factor of both and . In order to find the GCD of two non-negative integers, we use the Euclidean Algorithm, which is as follows:

This algorithm is very easy to implement using a recursive function, as follows:

Java

public int gcd(int a, int b){
if (b == 0) return a;
return gcd(b, a % b);
}

C++

int gcd(int a, int b){
if (b == 0) return a;
return gcd(b, a % b);
}

For C++14, you can use the built-in __gcd(a,b).

Python

def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)

This function runs in time because .

The worst-case scenario for the Euclidean algorithm is when and are consecutive Fibonacci numbers and . for an explanation). In this case, the algorithm will calculate . This means that finding takes steps, which is proportional to .

LCM

The least common multiple (LCM) of two integers and is the smallest integer divisible by both and . The LCM can easily be calculated from the following property with the GCD:

Warning!

Coding as a * b / gcd(a, b) might cause integer overflow if the value of a * b is greater than the max size of the data type of a * b (e.g. the max size of int is around 2 billion). Dividng a by gcd(a, b) first, then multiplying it by b will prevent integer overflow if the result fits in an int.

If we want to take the GCD or LCM of more than two elements, we can do so two at a time, in any order. For example,

C++

Exercise: What's wrong with the following code?

ll gcd(ll a, ll b){ return b == 0 ? a : gcd(b,a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }
int main() { cout << lcm(1000000000,999999999); } // output: 1808348672

Solution

Java

Python

Problems

StatusSourceProblem NameDifficultyTagsSolutionURL
ACEasy
Show Tags

Prime Factorization

Check AC
CSESNormal
CFNormal
Show Tags

Prime Factorization

CSESHard

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Give Us Feedback on Divisibility!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.

PrevNext