为什么我无法在链表中获取给定数字的 return 个质因数？我添加了 structure,function,main 和 print 函数

Question

我正在尝试查找给定数字 N 的质因数，并且 return 它们在链接中 list.There 查找质因数不是问题，但我遇到 return 问题将它们放入链表中...当我运行代码时我没有收到错误，但我只得到第一个素数作为输出，无法得到其余的，例如，如果 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\t",temp->data);
        temp=temp->next;
    }
  }

  int main()
  {
    SLLI*pHead=NULL;

    pHead=PrimeFactor(pHead,72);

    Printlist(pHead);


  }

Answer 1

我怀疑你只是没有正确地打印出来，这很难说，因为你没有包含该代码，但是，如果你这样添加 main：

int main(void) {
    SLLI * x = PrimeFactor(NULL, 72);
    while (x != NULL) {
        printf("%d\n", 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，六的倍数；
- 6n + 2 = 2(3n + 1),二的倍数;
- 6n + 3 = 3(2n + 1)，三的倍数；
- 6n + 4 = 2(3n + 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('\n');
}

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

为什么我无法在链表中获取给定数字的 return 个质因数？我添加了 structure,function,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

c

linked-list

data-structures

singly-linked-list