Является ли рекурсивно-итеративный метод лучше, чем чисто итеративный метод, чтобы узнать, является ли число простым?

Question

Я сделал эту программу на C, которая проверяет, является ли число простым. Я пока не знаком со сложностью Алгоритма и всеми этими вещами Big O, поэтому я не уверен, что мой подход, который является комбинацией итерации и рекурсии, на самом деле более эффективен, чем использование чисто итеративного метода.

#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef struct primenode{
    long int key;
    struct primenode * next;
}primenode;

typedef struct{
    primenode * head;
    primenode * tail;
    primenode * curr;
    unsigned long int size;
}primelist;

int isPrime(long int number, primelist * list ,long int * calls, long int * searchcalls);
primenode * primelist_insert(long int prime, primelist * list);
int primelist_search(long int searchval, primenode * searchat, long int * calls);
void primelist_destroy(primenode * destroyat);

int main(){
    long int n;
    long int callstoisprime = 0;
    long int callstosearch = 0;
    int result = 0;
    primelist primes;

    //Initialize primelist
    primes.head = NULL;
    primes.tail = NULL;
    primes.size = 0;

    //Insert 2 as a default prime (optional step)
    primelist_insert(2, &primes);

    printf("\n\nPlease enter a number: ");
    scanf("%d",&n);
    printf("Please wait while I crunch the numbers...");
    result = isPrime(n, &primes, &callstoisprime, &callstosearch);
    switch(result){
        case 1: printf("\n%ld is a prime.",n); break;
        case -1: printf("\n%ld is a special case. It's neither prime nor composite.",n); break;
        default: printf("\n%ld is composite.",n); break;
    }
    printf("\n\n%d calls made to function: isPrime()",callstoisprime);
    printf("\n%d calls made to function: primelist_search()",callstosearch);

    //Print all prime numbers in the linked list
    printf("\n\nHere are all the prime numbers in the linked list:\n\n");
    primes.curr = primes.head;
    while(primes.curr != NULL){
        printf("%ld ", primes.curr->key);
        primes.curr = primes.curr->next;
    }
    printf("\n\nNote: Only primes up to the square root of your number are listed.\n"
                "If your number is negative, only the smallest prime will be listed.\n"
                "If your number is a prime, it will itself be listed.\n\n");

    //Free up linked list before exiting
    primelist_destroy(primes.head);

    return 0;
}

int isPrime(long int number, primelist * list ,long int * calls, long int *searchcalls){
//Returns 1 if prime
//          0 if composite
//          -1 if special case
    *calls += 1;
    long int i = 2;
    if(number==0||number==1){
        return -1;
    }
    if(number<0){
        return 0;
    }
    //Search for it in the linked list of previously found primes
    if(primelist_search(number, list->head, searchcalls) == 1){
        return 1;
    }
    //Go through all possible prime factors up to its square root
    for(i = 2; i <= sqrt(number); i++){ 
        if(isPrime(i, list,calls,searchcalls)){
            if(number%i==0) return 0; //It's not a prime
        }
    }
    primelist_insert(number, list); /*Insert into linked list so it doesn't have to keep checking
                                                if this number is prime every time*/
    return 1;
}

primenode * primelist_insert(long int prime, primelist * list){
    list->curr = malloc(sizeof(primenode));
    list->curr->next = NULL;

    if(list->head == NULL){
        list->head = list->curr;
    }
    else{
        list->tail->next = list->curr;
    }
    list->tail = list->curr;
    list->curr->key = prime;
    list->size += 1;

    return list->curr;
}

int primelist_search(long int searchval, primenode * searchat, long int * calls){
    *calls += 1;
    if(searchat == NULL) return 0;
    if(searchat->key == searchval) return 1;
    return primelist_search(searchval, searchat->next, calls);
}

void primelist_destroy(primenode * destroyat){
    if(destroyat == NULL) return;
    primelist_destroy(destroyat->next);
    free(destroyat);
    return;
}

В основном, то, что я видел в простых тестах на примитивы, таково: 0. 2 - простое число. 1. Переберите все целые числа от 2 до половины или квадратный корень проверяемого числа. 2. Если число делится на что-либо, сломайте и верните false; это композитный. 3. В противном случае верните true после последней итерации; это главное.

Я подумал, что вам не нужно проверять каждое число от 2 до квадратного корня, только каждое простое число, потому что все остальные числа кратны простым. Итак, функция вызывает себя, чтобы выяснить, является ли число простым, прежде чем использовать модуль для него. Это работает, но я подумал, что немного утомительно продолжать проверять все эти простые числа снова и снова. Итак, я использовал связанный список для хранения всех найденных в нем простых чисел, поэтому перед проверкой простоты программа сначала ищет список.

Это действительно быстрее, или более эффективно, или я просто потратил много времени? Я проверил это на своем компьютере, и для больших простых чисел это показалось быстрее, но я не уверен. Я также не знаю, использует ли он значительно больше памяти, поскольку Диспетчер задач просто сохраняет постоянные 0,7 МБ независимо от того, что я делаю.

Спасибо за любые ответы!

Answer 1

Поскольку ваша программа тестирует только одно число, вы теряете время, пытаясь избежать тестирования композитами. Вы выполняете много вычислений, чтобы сохранить одну скудную операцию по модулю.

Если вы проверяете более чем несколько чисел в ряду на простоту, то имеет смысл предварительно вычислить простые числа до квадрата верхнего предела этого диапазона и пройти через эти простые числа при тестировании кандидатов.

Еще лучше будет выполнить сито Эратосфена ( код С здесь), чтобы найти простые числа в заданном диапазоне. Временная сложность сита Эратосфена для нахождения простых чисел от 2 до N равна O(N log log N); и пробное деление на простые числа до площади, O(N^1.5 / (log N)^2) (что еще хуже; например, соотношение времени пробега для сита до 1 млн. по сравнению с 100k составляет 10,7x против 22x для пробного разделения; 2 млн против 1 млн составляет 2,04x для сита, 2,7x для пробного разделения).

Псевдокод для офсетного сита Эратосфена:

Input: two Integers n >= m > 1

Let k = Floor(Sqrt(n)),
Let A be an array of Boolean values, indexed by Integers 2 to k, and
    B an array of Booleans indexed by Integers from m to n,
    initially all set to True.

for i = 2, 3, 4, ..., not exceeding k:
  if A[i] is True:
    for j = i^2, i^2+i, i^2+2i, ..., not greater than k:
      A[j] := False
    for j = i^2, i^2+i, i^2+2i, ..., between m and n, inclusive:
      B[j] := False

Output: all `i`s such that B[i] is True, are all the primes 
                                     between m and n, inclusive.

Распространенной оптимизацией является работа только с коэффициентами, i = 3,5,7,...избегая любых четных чисел с самого начала (в любом случае известно, что 2 простое число, а любое четное число является составным). Тогда шаг 2i и не только i, можно использовать в обоих внутренних циклах. Таким образом, четные индексы вообще исключаются из обработки (обычно с использованием схем сжатой адресации, val = start + 2*i).

Answer 2

Следующий фрагмент может быть значительно улучшен:

//Go through all possible prime factors up to its square root
for(i = 2; i <= sqrt(number); i++){ 
    if(isPrime(i, list,calls,searchcalls)){
        if(number%i==0) return 0; //It's not a prime
    }
}

Вместо циклического перебора всех чисел, просто перебирайте числа в связанном списке:

// Go through all possible prime factors up to its square root
primenode *p;
for (p = primes.head; p->key <= sqrt(number); p = p->next) { 
        if (number%(p->key) == 0) return 0; //It's not a prime
    }
}