为什么我无法在链表中得到给定数字的返回素数?

问题描述 投票:0回答:1

我正在尝试查找给定数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;
}
c data-structures linked-list singly-linked-list
1个回答
0
投票

[我怀疑您只是没有正确地打印它们,由于您没有包含该代码,因此很难说,但是如果您这样添加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为您提供235120 = 233151 (8 x 3 x 5)


要考虑的其他几点:

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

  • 当检查素数时,您不必将值取一半,只需取其平方根即可。因此,更好的循环是:for (j = 2; j * j <= i; j++)

  • 偶数[[更好检查是要认识到,除23之外,每个素数均采用6n + 16n + 5的形式。那是因为:

      [6n + 0 = 6n,六的倍数;]
    • [6n + 2 = 2(3n + 1),两个的倍数;]
    • [6n + 3 = 3(2n + 1),三的倍数;]
    • [6n + 4 = 2(3n + 2),两个的倍数;]
  • 仅保留6n + 16n + 5作为候选项(不是每个

    one

  • 都是素数(例如,6(4) + 1 = 25),但是素数can
仅从该集合中得出)。] >所以一个更好的素数检验是:

// Set initial primality based on multiple of 2 or 3. isPrime = (i % 2 != 0) && (i % 3 != 0); // Efficient selection of candidate primes, starting at 5, adding // 2 and 4 alternately: 5, 7, 11, 13, 17, 19, 21, 25, 27, ... for (j = 5, add = 2; isPrime && j * j <= i; j += add, add = 6 - add) if (i % j == 0) isPrime = 0; // isPrime now set correctly.

© www.soinside.com 2019 - 2024. All rights reserved.