Гауссовы целые числа

[Bod_r]

Помогите пожалуйста написать вот такую штуку . Заранее благодарен


Дано целое Гаусово число n + mi (принадлежащее Z ).
Требуется:
- Проверить является ли оно простым (в Z ).
- Вывести его разложение на простые (в Z ) множители.

[Romeo]

Это заказ программы за деньги или нужна помощь? Если заказ, то я перемещу в другой раздел. Если просто нужна помощь, то задавай более конкретные вопросы. Что именно не понятно или не знаешь как сделать?

[Bod_r]

незнаю как сделать

[Romeo]

Ну раз уж ты поленился предоставить теорию для тех, кто не понимает (или забыл) что такое комплексное число или гауссово число (две буквы "с" обязательны), то теорию предоставлю я (ссылка на Википедию).

И так, по критерию Гаусса, Гауссово число a + bi является простым тогда и только тогда, когда:
* либо одно из чисел a, b нулевое, а другое — целое простое число вида +-(4n+3);
* либо a, b оба не нули и норма a*a + b*b — простое натуральное число.

Думаю, этого определения более, чем достаточно, для того, чтобы решить первый пункт из задачки.

Далее по поводу второго пункта. Очевидно, что его следует выполнять только в том случае, если гауссово число не являеся простым. Поиск делителей будет несколько усложнён тем фактом, что число комплексное, однако усложнение выразится только в сложности алгоритма, так как однократный поиск делителя мы будем делать двумя вложенными циклами вместо одно цикла в случае натуральных чисел.

Поиск делителя, как и в случае натуральных чисел, сводится к проверке кандидата на делимость. Гауссово число по определению имеет целые Re и Im, а также известно, что кандидат по норме не может быть больше, чем исходное число по норме. Исходя из всего этого, перебор кандидатов не представляет никакой сложности - простой цикл в цикле (один по вещественной, другой по мнимой части числа).

Пробуй реализовать и задавай вопросы, если что-то не будет получаться. Будем помогать. Если передумал писать сам, то дай знать и я перенесу в раздел заказов.

[Bod_r]

о) спасибо за информацию!
буду пробовать

[Taras]

У меня такая же задача, она из задачника А. Шенна. Первую часть задания реализовал...а вот алгоритм разложения на простые числа не могу найти . Помогите плиззз.

[Bod_r]

У меня такая же задача, она из задачника А. Шенна. Первую часть задания реализовал...а вот алгоритм разложения на простые числа не могу найти . Помогите плиззз.

как ты первую часть зделал???

[rrrFer]

Код: Выделить всё

#include<iostream>
using std::cin;
using std::cout;
using std::endl;
bool checkEasy(int a){
	int i,n;
	for(i=2,n=a/2+1;i<n;i++)
		if(!(a%i))
			return 0;
	return 1;
}
bool checkEasy(int a, int b){
	if(!(a*b))
		return !((a+b-3)%4);
	return checkEasy(a*a+b*b);
}
int main(){
	int a,b;
	cin>>a>>b;
	cout<<checkEasy(a,b);
	cout<<endl<<"press any key to continue: "<<endl;
	cin.get(),cin.get();
	return 0;
}

первая часть

[Bod_r]

алгоритм продолжения я уже дописал ... позже выложу

[Bod_r]

Первую часть переделал, поскольку, она работала не со всеми числами. Дописал вторую часть. Если число Гаусса простое, то происходит розложение на простые множители. Вроде работает так как надо. =)

Код: Выделить всё

#include <iostream>
#include <math.h>
#include <conio.h>
using namespace std;
bool checkEasy(int a, int b)
{
	
    if(a==0)
	{
	    for(int i=2;i<b;i++)
		{
			if(b%i==0)
			{
				return 0;
			}
		}
		return 1;
	}
    if(b==0)
	{
	    for(int i=2;i<a;i++)
		{
			if(a%i==0)
			{
				return 0;
			}
		}
		return 1;
	}
    for(int i=2;i<(a*a+b*b);i++)
	{
		if((a*a+b*b)%i==0)
		{
			return 0; 
		}
	}
    return 1;
	
}
void R(int a, int b)
{
	for (int i=2;i<=a;i++)
	{
		for (int j=2;j<a;j++)
		{ 
		   
			if (a%i==0 && a%j!=0)
			{
				a=a/i;
				cout <<i<<endl;
			}	
		}
	}
	for (int i=2;i<=b;i++)
	{
		for (int j=2;j<b;j++)
		{
		   
			if (b%i==0 && b%j!=0)
			{
				b=b/i;
				cout <<i<<endl;
			}
		}	
	}
} 

int main(){
    int a,b;
    cin>>a>>b;
    bool c = checkEasy(a,b);
	cout<< c;
	cin.get(),cin.get();
	if(c==1)
	{
		cout<<"Easy"<<endl;
		R(a,b);
	}
	else
	{
		cout<<"not easy";
	}
		



	getch();
    return 0;
}