整数的质因数分解
程序员文章站
2022-05-11 20:29:18
...
整数的质因数分解
// 质因数分解.cpp: 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include"conio.h"
#include"math.h"
#include"malloc.h"
typedef long long prime;
typedef int index;
typedef struct PN//构造素数节点
{
union
{
prime data;
long long length;
};
struct PN *next;
}PN;
typedef struct PF//构造质因数分解
{
prime data;
index power;
struct PF *next;
}PF;
static PN* PNApplyNode(prime x)//申请新的素数结点
{
PN* s = (PN*)malloc(sizeof(PN));
if (s == NULL)
return NULL;
s->data = x;
s->next = NULL;
return s;
}
static PF* PFApplyNode(prime x, index P)//申请新的素数结点
{
PF* s = (PF*)malloc(sizeof(PF));
if (s == NULL)
return NULL;
s->data = x;
s->power = P;
s->next = NULL;
return s;
}
void PNListInitiate(PN *head)//素数列表初始化
{
head = (PN*)malloc(sizeof(PN));
head->next = NULL;
head->length = 0;
}
void PFListInitiate(PF *head)//质因数分解列表初始化
{
head = (PF*)malloc(sizeof(PF));
head->next = NULL;
}
bool PNInsert(PN* p, prime x)//素数新旧节点连接
{
if (p == NULL)
return false;
p->next = PNApplyNode(x);
return true;
}
bool PFInsert(PF* p, prime x,index P)//质因数分解新旧节点连接
{
if (p == NULL)
return false;
p->next = PFApplyNode(x, P);
return true;
}
void ShowPN(PN* head)//呈现素数列表内容
{
PN* p = head->next;
while (p != NULL)
{
printf("%lld\n", p->data);
p = p->next;
}
}
void ShowPF(PF* head)//呈现质因数分解结果
{
PF* p = head->next;
while (p != NULL)
{
printf("%lld %d \n", p->data, p->power);
p = p->next;
}
}
PN* Prime(long long N)//求N以内的素数
{
long long i, j;
long long k = 0;
long long count;
PN* head = (PN*)malloc(sizeof(PN));
PNListInitiate(head);
PN* p = head;
PN* h = head;
for (i = 2; i <= floor(sqrt(N)); i++)//计算前N^1/2中含有的素数
{
for (j = 2; j <= floor(sqrt(i)); j++)
if (i%j == 0)
break;
if (j > floor(sqrt(i)))
{
PNInsert(p, i);
p = p->next;
count = i;
k++;
head->length += 1;
}
}
for (i = count + 1; i < N; i++)//计算利用爱拉托斯散筛法计算N以前的所有素数
{
long long n = 0;//利用n判断该数i是否是整除N^1/2中任意素数的倍数
h = head;
for (j = 0; j < k; j++)
{
if (i % (h->next->data) != 0)
{
h = h->next;
n++;
continue;
}
}
if (n == k)
{
PNInsert(p, i);
p = p->next;
//printf("%lld\n", p->data);
head->length += 1;
}
}
return head;
}
PF* PrimeFactorization(long long X)//质因数分解
{
PF* head = (PF*)malloc(sizeof(PF));
PFListInitiate(head);
PF* p = head;
PN * A = Prime(1000000);
while (X != 1)
{
int count=0;
while (X % (A->next->data) == 0)
{
X = X / A->next->data;
count += 1;
}
if (count > 0)
{
PFInsert(p, A->next->data, count);
p = p->next;
}
A = A->next;
}
free(A);
return head;
}
int main()
{
PF * A = PrimeFactorization(349973300);
ShowPF(A);
free(A);
_getch();
return 0;
}
这里我进行一个样例的展示: 对
349973300
349973300
349973300进行质因数分解.
得到如下结果:
这就说明了:
349973300
=
2
2
5
2
123
1
1
284
3
1
349973300=2^25^21231^12843^1
349973300=22521231128431
编译器版本为VS2017, 不同编译器运行我的代码可能需要进行简单调试。