递归迭代方法是否比纯迭代方法更好地确定一个数字是否为素数? [英] Is a Recursive-Iterative Method Better than a Purely Iterative Method to find out if a number is prime?

问题描述

我用 C 语言编写了这个程序，用于测试 数字是否为素数.我还不熟悉算法复杂性和所有大 O 的东西，所以我不确定我的方法是迭代和递归的组合，实际上是否比使用 纯迭代方法.

I made this program in C that tests if a number is prime. I'm as yet unfamiliar with Algorithm complexity and all that Big O stuff, so I'm unsure if my approach, which is a combination of iteration and recursion, is actually more efficient than using a purely iterative method.

#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("

Please 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("
%ld is a prime.",n); break;
        case -1: printf("
%ld is a special case. It's neither prime nor composite.",n); break;
        default: printf("
%ld is composite.",n); break;
    }
    printf("

%d calls made to function: isPrime()",callstoisprime);
    printf("
%d calls made to function: primelist_search()",callstosearch);

    //Print all prime numbers in the linked list
    printf("

Here are all the prime numbers in the linked list:

");
    primes.curr = primes.head;
    while(primes.curr != NULL){
        printf("%ld ", primes.curr->key);
        primes.curr = primes.curr->next;
    }
    printf("

Note: Only primes up to the square root of your number are listed.
"
                "If your number is negative, only the smallest prime will be listed.
"
                "If your number is a prime, it will itself be listed.

");

    //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;
}

基本上，我见过的很多简单的 primalty 测试都是:0. 2 是素数.1. 循环遍历从 2 到一半或被测试数字的平方根的所有整数.2.如果数能被任何东西整除，则break并返回false；它是复合的.3.否则，最后一次迭代后返回true；这是主要的.

Basically, a lot of what I've seen simple primalty tests do is: 0. 2 is a prime. 1. Cycle through all integers from 2 to half or the square root of the number being tested. 2. If the number is divisible by anything, break and return false; it's composite. 3. Otherwise, return true after the last iteration; it's prime.

我认为您不必针对从 2 到平方根的每个数字进行测试，只需针对每个 素数 数字进行测试，因为所有其他数字都是素数的倍数.因此，该函数调用自身来确定一个数字是否为素数，然后再对其使用模数.这行得通，但我认为一遍又一遍地测试所有这些素数有点乏味.因此，我也使用了一个链表来存储在其中找到的每个素数，以便在测试素数之前，程序首先搜索该列表.

I figured that you don't have to test against every number from 2 to the square root, just every prime number, because all other numbers are multiples of primes. So, the function calls itself to find out if a number is prime before using the modulus on it. This works, but I thought it a bit tedious to keep testing all those primes over and over again. So, I used a linked list to store every prime found in it as well, so that before testing primalty, the program searches the list first.

它真的更快，或更高效，还是我只是浪费了很多时间?我确实在我的电脑上对其进行了测试，对于较大的素数，它确实看起来更快，但我不确定.我也不知道它是否使用了更多的内存，因为无论我做什么，任务管理器都保持恒定的 0.7 MB.

Is it really faster, or more efficient, or did I just waste a lot of time? I did test it on my computer, and for the larger primes it did seem faster, but I'm not sure. I also don't know if it uses significantly more memory since Task Manager just stays a constant 0.7 MB whatever I do.

感谢您的任何回答！

推荐答案

由于您的程序只测试一个数字，因此您正在浪费时间试图避免使用复合材料进行测试.您执行大量计算以节省一次微不足道的模运算.

Since your program tests just one number, you're wasting time trying to avoid testing by composites. You perform a lot of computations to save one meager modulo operation.

如果您要连续测试多个数字的素数，那么将素数预先计算到该范围上限的 sqrt 并在测试候选者时检查这些素数是有意义的.

If you were testing more than a few numbers in a row for primality, then it would make sense to pre-compute the primes up to a sqrt of the top limit of that range, and go through those primes when testing the candidates.

更好的是执行偏移 埃拉托色尼筛(此处为 C 代码)，查找给定范围内的素数.埃拉托色尼筛法从 2 到 N 求素数的时间复杂度为O(N log log N)；和试除以素数到 sqrt，O(N^1.5/(log N)^2)(更糟；例如 运行时间的比率对于高达 100 万的筛子与 100k 的筛子相比是 10.7 倍，而试验部门是 22 倍；20 万对 1 百万是 2.04 倍筛子，2.7x 为试除法).

Better yet will be to perform an offset sieve of Eratosthenes (C code here), to find the primes in a given range. The time complexity of the sieve of Eratosthenes to find primes from 2 to N is O(N log log N); and trial division by primes up to the sqrt, O(N^1.5 / (log N)^2) (which is worse; e.g. the ratio of run times for the sieve up to 1mln compared to 100k is 10.7x, vs 22x for trial division; 2mln vs 1 mln is 2.04x for the sieve, 2.7x for the trial division).

Eratosthenes 偏移筛的伪代码:

Pseudocode for the offset sieve of Eratosthenes:

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).

A common optimization is to work with odds only, i = 3,5,7,..., avoiding any even numbers from the outset (2 is known to be a prime anyway, and any even number is a composite). Then the step of 2i, and not just i, can be used in both inner loops. Thus the even indices are excluded from processing altogether (usually with condensed addressing schemes, val = start + 2*i).

这篇关于递归迭代方法是否比纯迭代方法更好地确定一个数字是否为素数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！