← Back to Overview

Divisibility Check (by N)

Concept Explanation

What is it?

Divisibility refers to the property of one integer being perfectly divisible by another integer, meaning the division results in an integer quotient with no remainder. When we say a number 'A' is divisible by 'N', it means that A % N (A modulo N) equals 0.

Why is it important?

Divisibility rules and checks are fundamental in arithmetic and programming. They are used in various algorithms, including: - Determining prime numbers. - Finding factors of a number. - Implementing scheduling or cyclic operations. - Data validation and formatting.

Where is it used?

• Checksums and Error Detection: Simple divisibility rules are sometimes part of algorithms to check for data integrity.
• Game Development: Creating patterns, determining turns, or checking conditions.
• Mathematical Algorithms: Any algorithm dealing with number properties often uses divisibility checks.
• User Input Validation: Ensuring that an entered number meets certain criteria (e.g., must be divisible by 100).

Real-world example

Imagine you have a certain number of items, say 15 apples. If you want to distribute them equally among 5 friends, you can check if 15 is divisible by 5. Since 15 % 5 == 0, each friend gets 3 apples with none left over. If you had 16 apples, 16 % 5 != 0, so you couldn't distribute them equally.

---

Algorithm

1. Start.
2. Get an integer (num) from the user.
3. Get the divisor (divisor_n) from the user. (For this example, we fix divisor_n to 5).
4. Calculate the remainder when num is divided by divisor_n (remainder = num % divisor_n).
5. If remainder is 0, then num is divisible by divisor_n.
6. Else, num is not divisible by divisor_n.
7. Display the result.
8. End.

Edge Cases: - Non-integer input (handled by language-specific error mechanisms or explicit validation). - divisor_n is 0: Division by zero must be prevented. - Negative numbers: Divisibility rules typically apply to positive integers, but modulo operator behavior with negative numbers can vary slightly between languages.

---

Implementations

Java (JDK 17)Python (3.10+)C (C99)Oracle (19c)

import java.util.Scanner;

public class DivisibleByN {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.print("Enter an integer: ");
        int number = scanner.nextInt();

        int divisor = 5; // For this example, check divisibility by 5

        System.out.println("Number entered: " + number);
        System.out.println("Checking divisibility by: " + divisor);

        if (number % divisor == 0) {
            System.out.println(number + " is DIVISIBLE by " + divisor + ".");
        } else {
            System.out.println(number + " is NOT divisible by " + divisor + ".");
        }

        scanner.close();
    }
}

# Get an integer from the user
num_str = input("Enter an integer: ")
num = int(num_str)

divisor = 5 # For this example, check divisibility by 5

print(f"Input Number: {num}")
print(f"Checking divisibility by: {divisor}")

if num % divisor == 0:
    print(f"{num} is DIVISIBLE by {divisor}.")
else:
    print(f"{num} is NOT divisible by {divisor}.")

#include <stdio.h>

int main() {
    int num;
    int divisor = 5; // For this example, check divisibility by 5

    printf("Enter an integer: ");
    scanf("%d", &num);

    printf("Input Number: %d\n", num);
    printf("Checking divisibility by: %d\n", divisor);

    if (num % divisor == 0) {
        printf("%d is DIVISIBLE by %d.\n", num, divisor);
    } else {
        printf("%d is NOT divisible by %d.\n", num, divisor);
    }

    return 0;
}

SET SERVEROUTPUT ON;
DECLARE
  input_num   NUMBER := &Enter_an_Integer;
  divisor_val NUMBER := 5; -- For this example, check divisibility by 5
BEGIN
  DBMS_OUTPUT.PUT_LINE('Input Number: ' || input_num);
  DBMS_OUTPUT.PUT_LINE('Checking divisibility by: ' || divisor_val);

  IF MOD(input_num, divisor_val) = 0 THEN
    DBMS_OUTPUT.PUT_LINE(input_num || ' is DIVISIBLE by ' || divisor_val || '.');
  ELSE
    DBMS_OUTPUT.PUT_LINE(input_num || ' is NOT divisible by ' || divisor_val || '.');
  END IF;
END;
/

Explanation

• Java: Uses the modulo operator (%) and an if-else statement. Scanner handles integer input.
• Python: Similar to Java, uses the modulo operator (%) and an if-else structure. input() reads as string, int() converts to integer.
• C: Reads integer input using scanf("%d", ...). The modulo operator (%) is used for the check within an if-else block.
• Oracle: Implemented in PL/SQL. Uses the MOD() function and IF-ELSE statements. Substitution variables (&Enter_an_Integer) allow for user input.

Complexity Analysis

• Time Complexity: O(1) - The number of operations is constant.
• Space Complexity: O(1) - A fixed number of variables are used.

Flowchart

graph TD
    A[Start] --> B[Get Integer num]
    B --> C[Set Divisor N (e.g., 5)]
    C --> D{num % N == 0?}
    D -- Yes --> E[Display DIVISIBLE]
    D -- No --> F[Display NOT DIVISIBLE]
    E --> G[End]
    F --> G

Sample Dry Run

Step	num	divisor_n	num % divisor_n	Description
Input	10	5	-	User enters 10
Process	10	5	0	Calculate 10 % 5
Decision	-	-	0 == 0? (True)	Remainder is 0
Output	-	-	-	Display "10 is DIVISIBLE by 5."
End	-	-	-	Program terminates
Input	7	5	-	User enters 7
Process	7	5	2	Calculate 7 % 5
Decision	-	-	2 == 0? (False)	Remainder is not 0
Output	-	-	-	Display "7 is NOT divisible by 5."
End	-	-	-	Program terminates

Practice Problems

Easy

• Modify the program to allow the user to input the divisor N.
• Check if a number is divisible by both 3 and 5.

Medium

• Write a program that finds all numbers divisible by N within a given range.
• Implement a function that returns True if a number is divisible by all numbers in a given list of divisors, otherwise False.

Hard

• Explore properties of divisibility (e.g., if a number is divisible by A and B, is it divisible by A*B? When?).

---

"Programming is the art of telling another human being what one wants the computer to do." - Donald Knuth