#include <iostream>
#include <stdio.h>
#include <string.h>

const int SPEICHER_GROESSE = 10;

struct Element {
    char* name;
    int wert;
    bool belegt;
};

unsigned long NameZuPlatz(const char* name) {
    unsigned long hash = 5381;
    int c;
    while ((c = *name++))
        hash = ((hash << 5) + hash) + c;
    return hash % SPEICHER_GROESSE;
}

// a) Funktion zum Eintragen eines Paares aus Name und Wert in den Speicher
void Eintragen(Element* speicher, char* name, int wert) {
    unsigned long index = NameZuPlatz(name); // 计算哈希索引
    // 若位置已被占用，直接覆盖；否则分配内存
    if (!speicher[index].belegt) {
        speicher[index].name = new char[strlen(name) + 1];
    }
    strcpy(speicher[index].name, name);
    speicher[index].wert = wert;
    speicher[index].belegt = true;
}

// b) Funktion zum Zurückgeben des Elements zu einem Namen
Element* NameZuElement(Element* speicher, char* name) {
    unsigned long index = NameZuPlatz(name);
    // 验证键是否匹配（防止哈希冲突）
    if (speicher[index].belegt && strcmp(speicher[index].name, name) == 0) {
        return &speicher[index];
    }
    return nullptr; // 未找到返回空指针
}

// c) Funktion zur Rückgabe der Summe aller Werte, deren Name mit einem bestimmten Zeichen beginnt
int SummeMitAnfangsbuchstabe(Element* speicher, char praefix) {
    int summe = 0;
    for (int i = 0; i < SPEICHER_GROESSE; i++) {
        if (speicher[i].belegt && speicher[i].name[0] == praefix) {
            summe += speicher[i].wert;
        }
    }
    return summe;
}

int main(int argc, char** argv)
{
    // Dynamisch Speicher zuweisen
    Element Speicher[SPEICHER_GROESSE] = {0};

    // Testbeispiele
    Eintragen(Speicher, (char*)"Alice", 10);
   // Eintragen(Speicher, (char*)"Bob", 20);
   // Eintragen(Speicher, (char*)"Alfred", 30);

    // Zum Testen einkommentieren:
   //printf("Wert von Alice: %d\n", NameZuElement(Speicher, (char*)"Alice")->wert);
    // printf("Wert von Bob: %d\n", NameZuElement(Speicher, (char*)"Bob")->wert);
    //printf("Summe der Werte mit Pr?fix 'A': %d\n", SummeMitAnfangsbuchstabe(Speicher, 'A'));

    Eintragen(Speicher, (char*)"YLSwc", 99); // 覆盖了Alice的的键值 
    // d) Kommentieren Sie die folgende Zeile ein und finden Sie den Grund für das Verhalten des Programms. Beschreiben Sie diesen.
     printf("Wert von Alice: %d", NameZuElement(Speicher, (char*)"Alice")->wert);

    return 0;
}

#include <iostream>
#include <stdio.h>
using namespace std;

// 函数：输出一个数的质因数分解
// 参数：zahl - 待分解的整数，ist_prim[] - 标记是否为质数的布尔数组
void gibPrimfaktorenAus(int zahl, bool ist_prim[]) {
    // 输出当前数字
    cout << zahl << ": ";

    // 如果该数是质数，直接输出"prim"并返回
    if (ist_prim[zahl]) {
        cout << "prim" << endl;
        return;
    }

    // 用于控制输出格式（第一个质因数前不加逗号）
    bool first = true;
    int temp = zahl;  // 保存原始数值，用于循环条件判断

    // 从最小的质数2开始，尝试所有可能的质因数
    for (int i = 2; i * i <= temp; i++) {
        // 如果i是质数，并且能整除当前数，则i是质因数
        while (ist_prim[i] && zahl % i == 0) {
            if (!first) {
                cout << ", ";  // 非第一个质因数前加逗号
            }
            cout << i;         // 输出质因数
            zahl /= i;         // 将原数除以该质因数
            first = false;     // 标记已输出至少一个质因数
        }
    }

    // 如果最后剩余的数大于1，说明它也是一个质因数（大于sqrt(temp)）
    if (zahl > 1) {
        if (!first) {
            cout << ", ";
        }
        cout << zahl;
    }

    cout << endl;
}

int main() {
    const int MAX = 1000;  // 定义上限

    // a) 在堆上动态分配布尔数组，用于标记每个数是否为质数
    bool* ist_prim = new bool[MAX];

    // 初始化：假设所有数都是质数
    for (int i = 0; i < MAX; i++) {
        ist_prim[i] = true;
    }

    // 特殊处理：0和1不是质数
    ist_prim[0] = ist_prim[1] = false;

    // b) 使用埃拉托斯特尼筛法（Sieve of Eratosthenes）找出1000以内的所有质数
    for (int i = 2; i < MAX; i++) {
        if (ist_prim[i]) {  // 如果i还未被标记为非质数
            // 将i的所有倍数标记为非质数（从i*i开始，因为小于i*i的倍数已被更小的质数标记）
            for (int j = i * i; j < MAX; j += i) {
                ist_prim[j] = false;
            }
        }
    }

    // 遍历2到999，输出每个数的质数状态或质因数分解
    for (int i = 2; i < MAX; i++) {
        if (ist_prim[i]) {
            // i是质数，直接输出
            cout << i << ": prim" << endl;
        } else {
            // i是合数，调用函数输出其质因数分解
            gibPrimfaktorenAus(i, ist_prim);
        }
    }

    // 释放动态分配的内存，防止内存泄漏
    delete[] ist_prim;

    return 0;
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com