Divisibility and Number Theory Basics

Number theory studies integer structure: which numbers divide others, how primes build numbers and what remainders reveal. These ideas appear in periodic schedules, grouping, factorization and modular computations. We begin with positive divisors and the distinction between mathematical floor division and C++ signed division. The program lists a number’s divisors, classifies it as prime/composite/neither, and demonstrates both division conventions on a signed input.

Prerequisites: Fundamentals: integer arithmetic, loops and vectors.

Build the idea

1. 1. Define divisors and multiples

   For integers d and n with d≠0, d divides n when n=d·k for an integer k. Then n is a multiple of d. This lesson lists positive divisors of positive n. A prime has exactly two positive divisors, 1 and itself; a composite integer greater than 1 has more. The number 1 is neither prime nor composite, and zero is outside the divisor-list contract because every positive integer divides it.

   $$n=d·k$$

2. 2. Find divisors in pairs

   If d divides n, n/d is a partner. At least one partner is at most √n, otherwise their product exceeds n. Scan d while d≤n/d to avoid overflow from d*d. Add both partners, but only once when they coincide for a perfect square. Sorting the gathered divisors gives increasing output. Later lessons derive more powerful formulas from prime powers.

3. 3. Recognize common decimal rules

   Even numbers end in 0,2,4,6,8; multiples of 5 end in 0 or 5; divisibility by 3 or 9 follows the digit sum; divisibility by 4 follows the final two decimal digits. These rules arise because powers of ten have simple remainders for those divisors. They are useful mental checks, not a substitute for a general remainder test d!=0 and n%d==0.

4. 4. Separate truncation from floor

   For positive b, mathematical division writes a=bq+r with 0≤r<b and q=floor(a/b). C++ integer division instead truncates toward zero, and its remainder has the dividend’s sign or is zero. Thus −7/3 is −2 and −7%3 is −1 in C++. To get the floor form, if the remainder is negative decrement q and add b to r. The identity a=bq+r then remains true.

   $$a=\mathrm{bq}+r$$

5. 5. Work the sample

   Twelve has divisor pairs (1,12),(2,6),(3,4), so the sorted list is 1,2,3,4,6,12 and it is composite. The signed demonstration prints C++ quotient/remainder −2,−1, then mathematical floor quotient/remainder −3,2. Both reconstruct −7, but only the second has nonnegative remainder. Input b must be positive; division by zero is never permitted.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Work the sample Twelve has divisor pairs (1,12),(2,6),(3,4), so the sorted list is
// 1,2,3,4,6,12 and it is composite.
#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    long long n,a,b;
    std::cin>>n>>a>>b;
    std::vector<long long>divisors;
    for(long long d=1;d<=n/d;++d){
        if(n%d==0){
            divisors.push_back(d);
            if(d!=n/d){
                divisors.push_back(n/d);
            }
        }
    }
    std::sort(divisors.begin(),divisors.end());
    for(int i=0;i<(int)divisors.size();++i){
        std::cout<<divisors[i]<<(i+1==(int)divisors.size()?'\n':' ');
    }
    std::cout<<(n==1?"NEITHER":divisors.size()==2?"PRIME":"COMPOSITE")<<'\n';
    long long q=a/b,r=a%b;
    std::cout<<q<<' '<<r<<'\n';
    if(r<0){
        --q;
        r+=b;
    }
    std::cout<<q<<' '<<r<<'\n';
}

Complexity analysis

O(√n+τ(n) log τ(n)) time including sorting the τ(n) divisors, O(τ(n)) output-list storage. Classification reuses that list; a primality-only test can stop earlier. Signed quotient adjustment is O(1). n≤10^6 keeps the demonstration small.

Example input and output

Read n a b, 1≤n≤10^6, |a|≤10^12, 1≤b≤10^6. Print positive divisors, classification, C++ quotient/remainder, then mathematical floor quotient/remainder.

Input

12 -7 3

Output

1 2 3 4 6 12
COMPOSITE
-2 -1
-3 2

Twelve has six divisors. Both −2·3−1 and −3·3+2 equal −7; only the latter uses 0≤r<3.

Practical applications

Use divisibility for grouping, periodicity and factor-based conditions. A sieve is better for many primality queries within one bounded range. Modular arithmetic formalizes remainders and safe operations; GCD captures the shared divisors of two integers.

Check your understanding

What is −7%3 in C++17?

Put it into practice

List divisors of 1, 36 and a prime.