题解 | #质数因子#

质数因子【不超时，全通过】【详解】【源码】【c】

1. 节省内存用链表存储，通过malloc()申请内存，注意引用<stdlib.h>库函数

2. 素因子更新

   • 用于测试的质数每次至少增加2（除了factor==2的情况）（只考虑奇数）
   • 用于测试的质数要先通过素性测试，否则再次加2，直到其通过素性测试

3. 因子判断及响应程序

   • 是因子，则更新待测数值，除以该因子，同时保证因子不变；
   • 不是因子，则更新素因子；

4. 结束条件：当测试的质数大于$\sqrt{N}\backslash sqrt\{N\}$时，程序结束，同时记录最后一个待测数值作为最大的因子

结束条件很关键，尤其是在题设的最大数字情况下，如果从0~N全部遍历的时间会超出时限， 尽管我不希望见到开根号计算，但它能减少的计算量太多了

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

struct node{
    int value;
    struct node* next;
};

typedef struct node Node;

int odd_prime_test( int x)// 奇数素性测试
{
    int tmp = 3; // 初值为3，不考虑因子为2的情况
    int r = sqrt(x)+1;
    
    while(tmp<r)
    {
        if(x/tmp*tmp==x)
            return 0; // 返回0，代表合数
        else
            tmp+=2;
    }
    return 1; // 返回1，代表素数
}

int main()
{
    Node head;  // 申请连接头节点
    Node* p = &head; // 申请节点指针，指向头节点
    head.value = 1;
    head.next = NULL;
    int n;
    scanf("%d",&n);
    int factor = 2; // 素因子从2开始计数
    
    while( factor*factor <= n)
    {
        if((n/factor)*factor == n) // 是因子
        {
            n = n/factor; // 更新待测数字
            //factor = factor;
            
            p->next = (Node*)malloc(sizeof(Node));  // 链表后新加节点，存储因子       
            p = p->next;
            p->value = factor;
            p->next = NULL;
        }
        else // 不是因子，因数+2
        {
            if(factor==2)
                factor=3;
            else
            {
                factor += 2;
                while(!odd_prime_test(factor)) // 如果因子非素，则加2；直至因子为素
                {
                    factor += 2;               
                }
            }       
        }     
    }
    // 跳出循环，将剩余数字作为最后的因子；该因子必素
    p->next = (Node*)malloc(sizeof(Node));  // add node          
    p = p->next;
    p->value = n;
    // 输出
    p = (&head)->next;
    while(p)
    {
        printf("%d ",p->value);
        p = p->next;
    }
    
    
    return 0;
}``