Слишком медленный генератор

Question

Я пытаюсь создать программу, которая ищет следующее простое число и добавляет его в список в текстовом файле.Однако эта программа все еще медленнее, чем та, что я делал в python.Я хотел бы сделать это быстрее.Я не знаю, поможет ли вместо постоянного чтения файла динамическая память.Если да, не могли бы вы помочь мне правильно его реализовать.Любое другое улучшение также приветствуется, так как я учусь

int root = 0, num = 0, p;
FILE *f;

int check_if_prime(){
    //calculates root to prevent calculating it at each step
    root = sqrt(p);
    //starts at the beginning of the file
    fseek(f, 0, SEEK_SET);
    //checks if p is prime
    num = 0;
    while (num <= root){
        fscanf(f, "%d", &num);
        if (p % num == 0) return 0;
    }
    return 1;
}

int main(){
    f = fopen("PATH", "a+");

    //prints all the numbers
    int last = 0;
    while (1){
        fscanf(f, "%d", &num);
        if (num == last) break;
        printf("\n %d", num);
        last = num;
    }

    //asks up to which number the program should calculate the primes
    int nmax;
    printf("\nnmax: ");
    scanf("%d", &nmax);

    //checks through the integers for primes and adds the to the file if they are
    for(int p = last + 2; p < nmax; p += 2){
        if (check_if_prime(p, f)){
            fseek(f, 0, SEEK_END);
            fprintf(f, "%d\n", p);
        }
    }

    //ends and restarts the program
    printf("\nPress 1 and enter\n\n\n");
    scanf("%d");
    fclose(f);
    main();
    return 0;
}

Answer 1

Я пытаюсь создать программу, которая ищет следующее простое число и добавляет его в список в текстовом файле.

Похоже, ваша программа пытается найти все простых чисел вплоть до введенного пользователем максимума, учитывая входной список простых чисел. Одним из относительно простых подходов к этому было бы использование сита с простыми числами, такого как Сито Эратосфена . Если вы можете предположить, что во входном файле не пропущены какие-либо простые числа в пределах диапазона, который он охватывает, то вы можете использовать его содержимое (по крайней мере, те, которые не превышают sqrt(nmax)) для частичной или полной инициализации сита. Вы захотите динамически распределять память для самого сита.

Это будет более эффективно, чем выполнение независимого теста на простоту (любого полезного вида) для каждого кандидата в целевом диапазоне. Поскольку вы изначально ограничиваете себя числами, представленными типом int, объем доступной памяти, вероятно, не является ограничивающим фактором, по крайней мере для настольного компьютера общего назначения, ноутбука или серверного компьютера.

Что касается ввода / вывода, вам нужно прочитать весь файл один раз, и вы должны написать каждое новое простое число, которое вы найдете. Обойти это невозможно. Но не делайте больше операций ввода-вывода, чем нужно. В частности, вам не нужно читать файл более одного раза, и, прочитав его до конца, вам не нужно искать в нем перед записью. Однако имеет смысл отложить чтение до тех пор, пока вы не введете nmax и не выделите массив sieve, интегрируя его с вашей реализацией sieve.

Обратите внимание, что если вы хотите найти только одно следующее простое число, тогда другой подход может быть более разумным.