Classic number programs · C++

These programs come up again and again in classes, tests and interviews. Each is a small function built from loops and conditions. Run each one, then change the numbers.

Leap years and prime numbers

A leap year divides by 4, except century years, which must also divide by 400. A prime has exactly two divisors; test divisors only while d * d <= n, because a bigger factor would pair with a smaller one already tested.

C++

#include <iostream>
using namespace std;

bool isLeap(int year) {
    return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}

bool isPrime(int n) {
    if (n < 2) return false;
    for (int d = 2; d * d <= n; d++) {
        if (n % d == 0) return false;
    }
    return true;
}

int main() {
    int years[4] = {2024, 2026, 1900, 2000};
    for (int i = 0; i < 4; i++) {
        cout << years[i] << (isLeap(years[i]) ? " is a leap year" : " is not a leap year") << endl;
    }
    int count = 0;
    for (int n = 2; n <= 50; n++) {
        if (isPrime(n)) {
            cout << n << " ";
            count++;
        }
    }
    cout << endl << count << " primes up to 50" << endl;
    return 0;
}

Fibonacci and swapping

C++

#include <iostream>
using namespace std;

int main() {
    int a = 0, b = 1;
    for (int i = 1; i <= 10; i++) {
        cout << a << " ";
        int next = a + b;
        a = b;
        b = next;
    }
    cout << endl;

    int x = 5, y = 9;
    int temp = x;          // the classic swap
    x = y;
    y = temp;
    cout << "after the swap: x = " << x << ", y = " << y << endl;
    return 0;
}

The standard library also has swap(x, y), which does the same in one line.

Palindromes and Armstrong numbers

A palindrome number reads the same reversed (121). An Armstrong number equals the sum of its digits, each raised to the number of digits (153 = 1 + 125 + 27):

C++

#include <iostream>
using namespace std;

int reverseNumber(int n) {
    int r = 0;
    while (n > 0) {
        r = r * 10 + n % 10;
        n /= 10;
    }
    return r;
}

bool isArmstrong(int n) {
    int digits = 0, rest = n, sum = 0;
    while (rest > 0) { digits++; rest /= 10; }
    rest = n;
    while (rest > 0) {
        int d = rest % 10, power = 1;
        for (int k = 0; k < digits; k++) power *= d;
        sum += power;
        rest /= 10;
    }
    return sum == n;
}

int main() {
    int tests[3] = {121, 12321, 123};
    for (int i = 0; i < 3; i++) {
        cout << tests[i] << (reverseNumber(tests[i]) == tests[i] ? " is a palindrome" : " is not a palindrome") << endl;
    }
    cout << "Armstrong numbers up to 1000: ";
    for (int n = 1; n <= 1000; n++) {
        if (isArmstrong(n)) cout << n << " ";
    }
    cout << endl;
    return 0;
}

GCD and LCM

Euclid's method replaces (a, b) with (b, a % b) until the remainder is 0. Then LCM = a x b / GCD:

C++

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main() {
    int x = 48, y = 36;
    cout << "GCD of " << x << " and " << y << " is " << gcd(x, y) << endl;
    cout << "LCM of " << x << " and " << y << " is " << x * y / gcd(x, y) << endl;
    return 0;
}