为什么我不能在链表中得到给定数字的返回素因数？我添加了结构、函数、Main和Print函数 [英] Why I can't get return prime factors of a given number in a linked list?I added the structure,function,main and the print function

问题描述

---

我正在尝试找到给定数字N的素因数并将它们返回到链接表中。查找素因数没有问题，但在链表中返回它们却有问题...运行代码时没有收到错误，但我只得到第一个素因数作为输出，不能得到其余的，例如，如果N等于72，我得到2作为输出，但不能得到其余的因数

    #include <stdio.h>
    #include <stdlib.h>
    //This is my structure
    typedef struct SinglyLinkedListItem
    {
        int data;
        struct SinglyLinkedListItem*next;
    }SLLI;

    //This is my function to find the prime factor and return in  a linked list
   SLLI*PrimeFactor(SLLI*prime,int N)
   {
    SLLI*pList=NULL;
    int i,j,isPrime;
    for (i = 2; i <= N; i++)
    {
        if(N % i == 0)
        {
            isPrime = 1;
            for (j = 2; j <= i/2; j++)
            {
                if(i % j == 0)
                {
                    isPrime = 0;
                    break;
                }
            }
            //Most probably problem is after this part of the code
            if(isPrime == 1)
            {
                //Adding first factor to the list
                if(pList==NULL)
                {
                    pList=malloc(sizeof(SLLI));
                    pList->data=i;
                    pList->next=NULL;
                    prime= pList;
                }

                //Trying to add rest of them but can't
                else
                {
                    pList->next = malloc(sizeof(SLLI));
                    pList->next->data = i;
                    pList->next->next = NULL;
                    pList = pList->next;
                }
            }
        }
   }
    return prime;
}

 void Printlist(SLLI*pHead)
 {
    SLLI*temp=pHead;
    while(temp!=NULL)
    {
        printf("%d	",temp->data);
        temp=temp->next;
    }
  }

  int main()
  {
    SLLI*pHead=NULL;

    pHead=PrimeFactor(pHead,72);

    Printlist(pHead);


  }

推荐答案

我怀疑您只是没有正确打印出来，很难判断，因为您没有包括该代码，但是，如果您添加了main，则如下所示：

int main(void) {
    SLLI * x = PrimeFactor(NULL, 72);
    while (x != NULL) {
        printf("%d
", x->data);
        x = x->next;
    }
    return 0;
}

然后您将得到2和3，这是72：72 = 2332 (8 x 9)的唯一素因数。

同样，120提供2、3和5：120 = 233151 (8 x 3 x 5)。

---

需要考虑的其他几点：

• 我不确定为什么要将prime传递给函数，因为您无论如何都会覆盖它。您应该将其从函数定义中删除，只使用一个局部变量来保存信息。

• 在检查素数时，您不需要到值的一半，只需要到它的平方根。因此更好的循环应该是：for (j = 2; j * j <= i; j++).

• 更好的检查是认识到，除了2和3之外，每个素数都是6n + 1或6n + 5的形式。这是因为：

  • 6n + 0 = 6n，6的倍数；
  • 6n + 2 = 2(3n + 1)，2的倍数；
  • 6n + 3 = 3(2n + 1)，三的倍数；
  • 6n + 4 = 2(3n + 2)，2的倍数；

只留下6n + 1和6n + 5作为候选(不是每个都有一个是素数(例如，6(4) + 1 = 25)，但素数可以完全从该集合中提取)。

因此，更好的素性检验是以下函数：

// Function for checking primality.

int isPrime(int number) {
    // Special cases.

    if ((number == 2) || (number == 3)) return 1;
    if ((number % 2 == 0) || (number % 3 == 0)) return 0;
    if (number < 5) return 0;

    // Efficient selection of candidate primes, starting at 5, adding
    // 2 and 4 alternately: 5, 7, 11, 13, 17, 19, 21, 25, 27, ...

    for (
        int candidate = 5, add = 2;
        candidate * candidate <= number;
        candidate += add, add = 6 - add
    ) {
        if (number % candidate == 0) {
            return 0;
        }
    }

    return 1;
}

---

使用该函数，添加一些额外的函数来转储和释放列表，并提供测试工具main，得到以下完整的程序：

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

typedef struct sListItem
{
    int data;
    struct sListItem *next;
} ListItem;

// Function for checking primality.

int isPrime(int number) {
    // Special cases.

    if ((number == 2) || (number == 3)) return 1;
    if ((number % 2 == 0) || (number % 3 == 0)) return 0;
    if (number < 5) return 0;

    // Efficient selection of candidate primes, starting at 5, adding
    // 2 and 4 alternately: 5, 7, 11, 13, 17, 19, 21, 25, 27, ...

    for (int candidate = 5, add = 2; candidate * candidate <= number; candidate += add, add = 6 - add)
        if (number % candidate == 0)
            return 0;

    return 1;
}

// Function for returning list of prime factors.

ListItem *primeFactorList(int number) {
    ListItem *retVal = NULL;
    ListItem *lastItem;

    // Analyse possible factors, up to half of number.

    for (int divisor = 2; divisor <= number / 2 + 1; divisor++) {
        if ((number % divisor == 0) && isPrime(divisor)) {
            if (retVal == NULL) {
                // Adding first item to list.

                retVal = lastItem = malloc(sizeof(ListItem));
                lastItem->data = divisor;
                lastItem->next = NULL;
            } else {
                // Adding subsequent items to list.

                lastItem->next = malloc(sizeof(ListItem));
                lastItem = lastItem->next;
                lastItem->data = divisor;
                lastItem->next = NULL;
            }
        }
    }

    return retVal;
}

// Dump a list.

void dumpList(int value, ListItem *head) {
    printf("%d:", value);
    while (head != NULL) {
        printf(" -> %d", head->data);
        head = head->next;
    }
    putchar('
');
}

// Free a list.

void freeList(ListItem *head) {
    while (head != NULL) {
        ListItem *toDelete = head;
        head = head->next;
        free(toDelete);
    }
}

// Test program.

int main(int argc, char *argv[]) {
    static int data[] = { 10, 24, 72, 120, 125, -1 };
    for (int *ptr = &(data[0]); *ptr >= 0; ptr++) {
        ListItem *list = primeFactorList(*ptr);
        dumpList(*ptr, list);
        freeList(list);
    }
    return 0;
}

和显示测试工具结果的编译和运行(右侧添加了我的注释，如果需要更多测试，可以随意向data数组添加任何附加值)：

10: -> 2 -> 5                   2 x 5
24: -> 2 -> 3                   2^3 x 3
72: -> 2 -> 3                   2^3 x 3^2
120: -> 2 -> 3 -> 5             2^3 x 3 x 5
125: -> 5                       5^3

这篇关于为什么我不能在链表中得到给定数字的返回素因数？我添加了结构、函数、Main和Print函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！