最大公约数、素数与进制

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){    当 (b != 0)    {        r = a % b; // (a, b)를 (b, a를 b로 나눈 나머지)로 바꾼다        a = b;        b = r;    }    返回 a;} toBase(x, base){    如果 (x == 0)    {        返回 "0";    }    s = "";    当 (x > 0)    {        s = DIGITS[x % base] + s; // 나머지는 낮은 자리부터 나오므로 앞에 붙인다        x = 数学.商(x, base);    }    返回 s;} ab = 控制台.读数字();n = 控制台.读行().转数字();xb = 控制台.读数字(); 控制台.输出(gcd(ab[0], ab[1])); // 체: 소수를 찾을 때마다 그 배수를 지운다. 끝까지 안 지워진 수가 소수isPrime = 新列表(n + 1, 真);isPrime[0] = 假;isPrime[1] = 假;循环 (i = 2; i * i <= n; i++){    如果 (isPrime[i])    {        循环 (j = i * i; j <= n; j += i)        {            isPrime[j] = 假;        }    }}primes = [];循环 (i = 2; i <= n; i++){    如果 (isPrime[i])    {        primes.添加(i);    }}控制台.输出(primes); 控制台.输出(toBase(xb[0], xb[1]));