是一个递归迭代方法比单纯的迭代法，以找出是否一个数是素更好？ [英] 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("\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;
}

基本上，很多我所看到的简单primalty测试要做的是：
0.2是一个素数。
1.循环通过从2至一半或数量的平方根的所有整数被测试。
2.如果数字是整除任何东西，突破和返回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的平方根，只是每次的主要的数量，因为所有其他的数字是素数的倍数。因此，函数调用自身，以找出是否一个数字是使用它的模前总理。这工作，但我认为它有点乏味，以保持一遍又一遍的测试所有的素数。
所以，我用一个链表来存储它发现以及每个素，从而使测试primalty之前，程序首先搜索列表中。

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.

如果你在一排素性测试以上几个数字越多，那么它会通过这些素数是有意义的pre-计算素数高达该区间的顶部极限开方和循环测试考生。

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 cycle through those primes in testing the candidates.

更重要的是将要执行的的偏移的的埃拉托色尼<筛/ em>的（ C $ C $这里 C），发现在给定范围内的素数。埃拉托色尼的筛找到2到N素数的时间复杂度为 O（N日志日志N）;和素数达开方审判庭， O（N ^ 1.5 /（日志N）^ 2）（这是慢得多;如的运行时间的比值筛高达1mln相比，100K为10.7倍，22倍VS审理分工; 2mln对1万是2.04x的筛子，2.7倍的审判庭）

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 much slower; 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).

伪code的埃拉托色尼的偏移筛：

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 =开始+ 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屋！