Verify Goldbach's conjecture

hash_table.c

//
// Created by Neuron on 2021/10/20.
//

#include "hash_table.h"

HashTable *initHashTable(uint64_t size) {
    HashTable *hashTable = (HashTable *) malloc(sizeof(HashTable));
    hashTable->count = size;
    hashTable->node = (Node **) calloc(size, sizeof(Node *));
}

uint64_t Hash(uint64_t key) {
    return pi(key);
}

void resizeHashTable(HashTable *hashTable, uint64_t new_size) {
    hashTable->node = (Node **) realloc(hashTable->node, new_size * sizeof(Node *));
    for (uint64_t i = hashTable->count; i < new_size; i++) {
        hashTable->node[i] = NULL;
    }
    hashTable->count = new_size;
}

uint64_t* insertHash(HashTable *hashTable, uint64_t key) {
    uint64_t addr = Hash(key);
    if (hashTable->node[addr] == NULL) {
        hashTable->node[addr] = (Node *) malloc(sizeof(Node));
        hashTable->node[addr]->elem = key;
        hashTable->node[addr]->nextNode = NULL;
        return &(hashTable->node[addr]->elem);
    } else {
        Node *node = hashTable->node[addr];
        while (node->nextNode != NULL) {
            node = node->nextNode;
        }
        node->nextNode = (Node *) malloc(sizeof(Node));
        node->nextNode->elem = key;
        node->nextNode->nextNode = NULL;
        return &(node->nextNode->elem);
    }
}

bool searchHash(HashTable *hashTable, uint64_t key) {
    uint64_t addr = Hash(key);
    if (hashTable->node[addr] == NULL) {
        return false;
    }
    Node *node = hashTable->node[addr];
    while (true) {
        if (node->elem == key) {
            return true;
        }
        if (node->nextNode == NULL) {
            return false;
        }
        node = node->nextNode;
    }
}

hash_table.h

//
// Created by Neuron on 2021/10/20.
//

#ifndef UNTITLED_HASH_TABLE_H
#define UNTITLED_HASH_TABLE_H

#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include "prime_number.h"
#include <assert.h>

typedef struct Node {
    uint64_t elem;
    struct Node *nextNode;
} Node;

typedef struct {
    Node **node;
    uint64_t count;
} HashTable;

HashTable *initHashTable(uint64_t size);

uint64_t Hash(uint64_t key);

uint64_t* insertHash(HashTable *hashTable, uint64_t key);

void resizeHashTable(HashTable *hashTable, uint64_t new_size);

bool searchHash(HashTable *hashTable, uint64_t key);

#endif //UNTITLED_HASH_TABLE_H

main.c

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdint.h>
#include "prime_number.h"

#pragma clang diagnostic push
#pragma ide diagnostic ignored "EndlessLoop"

int main(void) {

    while (true) {

        uint64_t n;
        printf("请输入一个不小于6的偶数，或不小于9的奇数:");
        scanf("%" PRIu64, &n);
        getchar();

        if ((n%2==0&&n<6)||(n%2==1&&n<9)) {
            printf("数据输入有误，请输入一个不小于6的偶数，或不小于9的奇数。\n");
            system("pause");
            continue;
        }

        uint64_t** prime_array = initPrime(n);

        //print_prime(n);

        test(n);


        if(n%2==0) {
            for(uint64_t i=0;prime_array[i]!=0&&*prime_array[i]<=n/2;i++) {
                uint64_t a = *prime_array[i];
                if(is_prime(n-a)) {
                    printf("%"PRIu64"=%"PRIu64"+%"PRIu64"\n",n,a,n-a);
                }
            }
        } else {
            for(uint64_t i=0;prime_array[i]!=NULL&&*prime_array[i]<=n/3;i++) {
                uint64_t a = *prime_array[i];
                for(uint64_t j=0; prime_array[j] != NULL && *prime_array[j] <= n / 3; j++) {
                    uint64_t b = *prime_array[j];
                    if(is_prime(n-a-b)) {
                        printf("%"PRIu64"=%"PRIu64"+%"PRIu64"+%"PRIu64"\n",n,a,b,n-a-b);
                    }
                }
            }
        }

        system("pause");
    }


}

#pragma clang diagnostic pop

prime_number.c

//
// Created by Neuron on 2021/10/20.
//

#include "prime_number.h"

uint64_t **prime_array = NULL;
uint64_t number = 0;
HashTable *hashTable = NULL;

uint64_t **initPrime(uint64_t n) {
    if (prime_array == NULL) {
        /*
         * 定义一个整数n，n为素数的上限。分配内存空间并初始化数组
         */
        if (n <= 1) {
            return NULL;
        }
        prime_array = (uint64_t **) calloc(pi(n)+1, sizeof(uint64_t*));
        hashTable = initHashTable(pi(n)+1);
        prime_array[0] = insertHash(hashTable, 2);
        number = n;
        if (n == 2) {
            return prime_array;
        }
        __initArray(n);
    } else {
        if (n <= number) {
            return prime_array;
        }
        uint64_t start = pi(number);
        prime_array = realloc(prime_array, sizeof(uint64_t*) * (pi(n)+1));
        uint64_t end = pi(n)+1;
        for (uint64_t i = start; i < end; i++) {
            prime_array[i] = NULL;
        }
        resizeHashTable(hashTable, n+1);
        _initArray(number, n);
        number = n;
    }
    return prime_array;
}

uint64_t pi(uint64_t n) {
    return ((uint64_t) (30.0 * log(113.0) / 113.0 * n / log(n)));
}

void __initArray(uint64_t end) {
    _initArray(3, end);
}

void _initArray(uint64_t start, uint64_t end) {
    uint64_t i = 0;
    while (true) {
        if (prime_array[i] == 0) {
            break;
        } else {
            i++;
        }
    }
    /*
     * 循环遍历start到end之间的每一个数，判断是否为素数。
     */
    for (uint64_t j = start; j <= end; j++) {
        uint32_t sqrt_i = sqrt(j);
        /*
         * 依次求i与[√i]之间的每一个数相除的余数，i%j==0说明余数是0，j是i的一个因子，i是素数，将number[i]设为false。
         * 全部遍历完后仍然为true就说明i是素数
         * 易证明，若i是合数，则i的最小因子必定小于或等于[√i]
         */
        for (uint64_t k = 0; true; k++) {
            if (*prime_array[k] > sqrt_i || prime_array[k] == 0) {
                prime_array[i++] = insertHash(hashTable, j);
                break;
            }
            if (j % *prime_array[k] == 0) {
                break;
            }
        }
    }
}

bool is_prime(uint64_t u) {
    return searchHash(hashTable, u);
}

void print_prime(uint64_t n) {
    /*
     * 循环遍历3到n的每一个数，判断是否为素数，是素数就输出
     */
    for (uint64_t i = 0; i <= n; i++) {
        if (prime_array[i] != NULL) {
            printf("%"PRIu64" ", *prime_array[i]);
        } else {
            break;
        }
    }
    printf("\n");
}

void test(uint64_t i) {
    for (int j = 0; j <= i && prime_array[j] != 0; j++) {
        assert(is_prime(*prime_array[j]));
    }
}

void finally() {
    free(prime_array);
    free(hashTable);
    prime_array = NULL;
    hashTable = NULL;
    number = 0;
}

prime_number.h

//
// Created by Neuron on 2021/10/20.
//
#ifndef UNTITLED_PRIME_NUMBER_H
#define UNTITLED_PRIME_NUMBER_H

#include <stdint.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <inttypes.h>
#include "hash_table.h"

/*
 * 初始化素数表
 */
uint64_t **initPrime(uint64_t n);

/*
 * 使用素数定理的近似估算素数上限并初始化存放素数的数组
 */
uint64_t pi(uint64_t n);

void __initArray(uint64_t end);

void _initArray(uint64_t start, uint64_t end);

void print_prime(uint64_t n);

void test(uint64_t i);

bool is_prime(uint64_t u);

/*
 * 释放内存
 */
void finally();

#endif //UNTITLED_PRIME_NUMBER_H