Algorithms · 30
GCD, primes and number bases
Find the GCD with remainders, sift out primes with a sieve, and write a number in another base.
These are three tools that keep turning up in number problems.
The example below finds the greatest common divisor of 84 and 36, prints every prime up to 30, and writes 255 in base 16.
DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz" def gcd(a, b): while b != 0: a, b = b, a % b # (a, b)를 (b, a를 b로 나눈 나머지)로 바꾼다 return a def to_base(x, base): if x == 0: return "0" s = "" while x > 0: s = DIGITS[x % base] + s # 나머지는 낮은 자리부터 나오므로 앞에 붙인다 x //= base return s a, b = map(int, input().split())n = int(input())x, base = map(int, input().split()) print(gcd(a, b)) # 체: 소수를 찾을 때마다 그 배수를 지운다. 끝까지 안 지워진 수가 소수is_prime = [True] * (n + 1)is_prime[0] = is_prime[1] = Falsei = 2while i * i <= n: if is_prime[i]: for j in range(i * i, n + 1, i): is_prime[j] = False i += 1primes = [i for i in range(2, n + 1) if is_prime[i]]print(*primes) print(to_base(x, base))const DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz"; function gcd(a, b) { while (b !== 0) { [a, b] = [b, a % b]; // (a, b)를 (b, a를 b로 나눈 나머지)로 바꾼다 } return a;} function toBase(x, base) { if (x === 0) return "0"; let s = ""; while (x > 0) { s = DIGITS[x % base] + s; // 나머지는 낮은 자리부터 나오므로 앞에 붙인다 x = Math.floor(x / base); } return s;} const [a, b, n, x, base] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number); console.log(gcd(a, b)); // 체: 소수를 찾을 때마다 그 배수를 지운다. 끝까지 안 지워진 수가 소수const isPrime = new Array(n + 1).fill(true);isPrime[0] = isPrime[1] = false;for (let i = 2; i * i <= n; i++) { if (isPrime[i]) { for (let j = i * i; j <= n; j += i) isPrime[j] = false; }}const primes = [];for (let i = 2; i <= n; i++) if (isPrime[i]) primes.push(i);console.log(primes.join(" ")); console.log(toBase(x, base));import { readFileSync } from "node:fs";const DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz"; function gcd(a: number, b: number): number { while (b !== 0) { [a, b] = [b, a % b]; // (a, b)를 (b, a를 b로 나눈 나머지)로 바꾼다 } return a;} function toBase(x: number, base: number): string { if (x === 0) return "0"; let s = ""; while (x > 0) { s = DIGITS[x % base] + s; // 나머지는 낮은 자리부터 나오므로 앞에 붙인다 x = Math.floor(x / base); } return s;} const [a, b, n, x, base] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number); console.log(gcd(a, b)); // 체: 소수를 찾을 때마다 그 배수를 지운다. 끝까지 안 지워진 수가 소수const isPrime: boolean[] = new Array(n + 1).fill(true);isPrime[0] = isPrime[1] = false;for (let i = 2; i * i <= n; i++) { if (isPrime[i]) { for (let j = i * i; j <= n; j += i) isPrime[j] = false; }}const primes: number[] = [];for (let i = 2; i <= n; i++) if (isPrime[i]) primes.push(i);console.log(primes.join(" ")); console.log(toBase(x, base));import java.util.Arrays;import java.util.Scanner; public class Main { static final String DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz"; static int gcd(int a, int b) { while (b != 0) { int r = a % b; // (a, b)를 (b, a를 b로 나눈 나머지)로 바꾼다 a = b; b = r; } return a; } static String toBase(int x, int base) { if (x == 0) return "0"; String s = ""; while (x > 0) { s = DIGITS.charAt(x % base) + s; // 나머지는 낮은 자리부터 나오므로 앞에 붙인다 x /= base; } return s; } public static void main(String[] args) { Scanner in = new Scanner(System.in); int a = in.nextInt(), b = in.nextInt(), n = in.nextInt(), x = in.nextInt(), base = in.nextInt(); System.out.println(gcd(a, b)); // 체: 소수를 찾을 때마다 그 배수를 지운다. 끝까지 안 지워진 수가 소수 boolean[] isPrime = new boolean[n + 1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) isPrime[j] = false; } } StringBuilder primes = new StringBuilder(); for (int i = 2; i <= n; i++) { if (isPrime[i]) primes.append(primes.length() > 0 ? " " : "").append(i); } System.out.println(primes); System.out.println(toBase(x, base)); }}using System;using System.Collections.Generic; class Program{ const string DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz"; static int Gcd(int a, int b) { while (b != 0) { (a, b) = (b, a % b); // (a, b)를 (b, a를 b로 나눈 나머지)로 바꾼다 } return a; } static string ToBase(int x, int b) { if (x == 0) return "0"; string s = ""; while (x > 0) { s = DIGITS[x % b] + s; // 나머지는 낮은 자리부터 나오므로 앞에 붙인다 x /= b; } return s; } static void Main() { string[] ab = Console.ReadLine().Split(); int a = int.Parse(ab[0]), b = int.Parse(ab[1]); int n = int.Parse(Console.ReadLine()); string[] xb = Console.ReadLine().Split(); int x = int.Parse(xb[0]), numBase = int.Parse(xb[1]); // base는 C#의 예약어라 이름을 바꿨다 Console.WriteLine(Gcd(a, b)); // 체: 소수를 찾을 때마다 그 배수를 지운다. 끝까지 안 지워진 수가 소수 bool[] isPrime = new bool[n + 1]; Array.Fill(isPrime, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) isPrime[j] = false; } } List<int> primes = new List<int>(); for (int i = 2; i <= n; i++) if (isPrime[i]) primes.Add(i); Console.WriteLine(string.Join(" ", primes)); Console.WriteLine(ToBase(x, numBase)); }}#include <iostream>#include <string>#include <vector> const std::string DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz"; int gcd(int a, int b) { while (b != 0) { int r = a % b; // (a, b)를 (b, a를 b로 나눈 나머지)로 바꾼다 a = b; b = r; } return a;} std::string toBase(int x, int base) { if (x == 0) return "0"; std::string s = ""; while (x > 0) { s = DIGITS[x % base] + s; // 나머지는 낮은 자리부터 나오므로 앞에 붙인다 x /= base; } return s;} int main() { int a, b, n, x, base; std::cin >> a >> b >> n >> x >> base; std::cout << gcd(a, b) << '\n'; // 체: 소수를 찾을 때마다 그 배수를 지운다. 끝까지 안 지워진 수가 소수 std::vector<bool> isPrime(n + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) isPrime[j] = false; } } std::vector<int> primes; for (int i = 2; i <= n; i++) if (isPrime[i]) primes.push_back(i); for (size_t k = 0; k < primes.size(); k++) std::cout << (k ? " " : "") << primes[k]; std::cout << '\n'; std::cout << toBase(x, base) << '\n';}#include <stdio.h>#include <string.h> const char *DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz";char isPrime[10001]; int gcd(int a, int b) { while (b != 0) { int r = a % b; // (a, b)를 (b, a를 b로 나눈 나머지)로 바꾼다 a = b; b = r; } return a;} // s에 x를 base진법으로 적는다void toBase(int x, int base, char *s) { char buf[40]; int len = 0; if (x == 0) buf[len++] = '0'; while (x > 0) { buf[len++] = DIGITS[x % base]; // 나머지는 낮은 자리부터 나온다 x /= base; } for (int i = 0; i < len; i++) s[i] = buf[len - 1 - i]; // 그래서 거꾸로 옮긴다 s[len] = '\0';} int main(void) { int a, b, n, x, base; scanf("%d %d %d %d %d", &a, &b, &n, &x, &base); printf("%d\n", gcd(a, b)); // 체: 소수를 찾을 때마다 그 배수를 지운다. 끝까지 안 지워진 수가 소수 memset(isPrime, 1, n + 1); isPrime[0] = isPrime[1] = 0; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) isPrime[j] = 0; } } int count = 0; for (int i = 2; i <= n; i++) { if (isPrime[i]) printf(count++ ? " %d" : "%d", i); } printf("\n"); char s[40]; toBase(x, base, s); printf("%s\n", s); return 0;}DIGITS = "0123456789abcdefghijklmnopqrstuvwxyz"; gcd(a, b){ while (b != 0) { r = a % b; // (a, b)를 (b, a를 b로 나눈 나머지)로 바꾼다 a = b; b = r; } return a;} toBase(x, base){ if (x == 0) { return "0"; } s = ""; while (x > 0) { s = DIGITS[x % base] + s; // 나머지는 낮은 자리부터 나오므로 앞에 붙인다 x = Mathf.Quot(x, base); } return s;} ab = Console.ReadNumbers();n = Console.ReadLine().ToNumber();xb = Console.ReadNumbers(); Console.WriteLine(gcd(ab[0], ab[1])); // 체: 소수를 찾을 때마다 그 배수를 지운다. 끝까지 안 지워진 수가 소수isPrime = NewList(n + 1, true);isPrime[0] = false;isPrime[1] = false;for (i = 2; i * i <= n; i++){ if (isPrime[i]) { for (j = i * i; j <= n; j += i) { isPrime[j] = false; } }}primes = [];for (i = 2; i <= n; i++){ if (isPrime[i]) { primes.Add(i); }}Console.WriteLine(primes); Console.WriteLine(toBase(xb[0], xb[1]));84 36 30 255 16
12 2 3 5 7 11 13 17 19 23 29 ff
Key points
- The greatest common divisor (GCD) is the largest number that divides both numbers.
Keep replacing(a, b)with(b, a % b)until b is 0, and the a that is left is the answer.
(84, 36) → (36, 12) → (12, 0), so it is 12. - This is correct because any number that divides both a and b also divides both b and
a % b, and the other way round.
The numbers shrink quickly: even with the slowest kind of input, two numbers close to a trillion finished in 57 laps. - A prime is a number greater than 1 that only 1 and itself divide.
To find every prime up to n, use a sieve.
Walk up from 2; a number that has not been crossed out yet is prime, and you cross out all of its multiples. - Start crossing out at
i * i.
Smaller multiples were already crossed out by a smaller prime.
For the same reason the outer loop only runs whilei * i <= n. - To write a number in another base, write down the remainder of dividing by the base, replace the number with the quotient, and repeat until it is 0.
The remainders come out lowest digit first, so put each one in front.
255 gives remainder 15 (f) and quotient 15, then remainder 15 (f) and quotient 0, so it isff. - The example does not do it, but to read such a string back as a number, go from the first character and repeat
x = x * base + digit.ffgoes 0 → 15 → 15 × 16 + 15 = 255.
Digits of 10 and above are written as letters, starting froma(10).
How each language writes it
| Python | There is math.gcd(a, b).Write in base 2, 8 or 16 with format(255, "b"), "o", "x" (→ ff); read with int("ff", 16).For other bases, write it yourself as in the example. The quotient is // |
|---|---|
| JavaScript | There is no GCD function, so write your own. Write with (255).toString(16) (→ ff), read with parseInt("ff", 16).The quotient is Math.floor(x / base) |
| TypeScript | Same as JavaScript |
| Java | There is no GCD function for int, so write your own (BigInteger does have gcd).Write with Integer.toString(255, 16), read with Integer.parseInt("ff", 16) |
| C# | There is BigInteger.GreatestCommonDivisor(a, b) (System.Numerics), but for int you can simply write your own.Convert.ToString(255, 16) and Convert.ToInt32("ff", 16) accept only bases 2, 8, 10 and 16 (3 throws ArgumentException) |
| C++ | std::gcd(a, b) in <numeric>.Read with std::stoi("ff", nullptr, 16); write it yourself as in the example.The sieve is a std::vector<bool> |
| C | There is no GCD function, so write your own. Read with strtol("ff", NULL, 16); write with printf's %x (base 16) and %o (base 8).For other bases, collect the digits backwards and then reverse them |
| Craykon | There are no GCD or base functions, so write them all yourself. The quotient is Mathf.Quot(x, base), a digit character is DIGITS[d], and a character's value is DIGITS.IndexOf(ch) |
Common mistakes
Converting 0 gave an empty string
def to_base(x, base):
s = ""
while x > 0:
s = str(x % base) + s
x //= base
return s
print("[" + to_base(0, 2) + "]")→ [] — nothing between the brackets. When x is 0 the loop never runs
Return "0" separately when x is 0.
Taking the quotient with /JavaScript · TypeScript · Craykon
let x = 5, s = "";
while (x > 0) {
s = (x % 2) + s;
x = x / 2;
}
console.log(s.length, s.slice(-12));→ 23085 .6251.250.51 — it should be 101, but the string is over 20,000 characters long. / keeps the fraction (2.5, 1.25, 0.625…), so x takes a very long time to reach 0
Take only the quotient: Math.floor(x / 2) in JavaScript, Mathf.Quot(x, 2) in Craykon.
i * i went past int in the sieveJava · C# · C++ · C
int n = 100000;
boolean[] isPrime = new boolean[n + 1];
Arrays.fill(isPrime, true);
for (int i = 2; i <= n; i++)
if (isPrime[i])
for (int j = i * i; j <= n; j += i) isPrime[j] = false;→ ArrayIndexOutOfBoundsException: Index -2146737495 out of bounds for length 100001 — at i = 46349, i * i passed about 2.1 billion and turned negative. C# throws IndexOutOfRangeException; C and C++ die with SIGSEGV
Run the outer loop only while i * i <= n.
With n at 100,000, i only goes up to 316.
How languages differ
Use a built-in when there is one, but some languages have none and some handle only bases 2, 8 and 16, so know how to write these yourself.
The least common multiple is
Divide first and multiply after, so the value in between stays smaller.
Use a built-in when there is one, but some languages have none and some handle only bases 2, 8 and 16, so know how to write these yourself.
The least common multiple is
a / gcd(a, b) * b (252 for 84 and 36).Divide first and multiply after, so the value in between stays smaller.