欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

整数的质因数分解

程序员文章站 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, 不同编译器运行我的代码可能需要进行简单调试。