Помогите оптимизировать индусокод

Дано число N.Нужно найти 2 числа A и B сумма который равна числу N=A+B и наибольший общий делитель этих чисел максимален.Нужна помощь в оптимизации,программа очень долго работает на больших числах на подобии 10^9.

#include <iostream>
#include <stdio.h>


using namespace std;

int nod(int a, int b)
{
	while ((a != 0) && (b != 0))
	{
		if (a > b)
			a = a-b;
		else b = b - a;
	}
	return (a);
}
int main()
{
	
	int n,a,b;
	cin >> n;
	int maxNod = 0;
	int maxA, maxB;
	b = n;
		for (int a = 1; a <= n/2; ++a)
		{
			
			b = n - a;
			if (nod(a, b) >= maxNod)
			{
				maxA = a;
				maxB = b;
				maxNod = nod(a, b);
			}

		}cout << maxA << " " << maxB;
		
	return 0;
}

const int primaries[] = {2,3,5,7,11,13,...}; // google "prime numbers table"

main()
{
	int n;
	cin >> n;
	if (n <= 1)
	{
		cout << "WTF?"
		return 1;
	}
	for (int i = 1; i <= sizeof(primaries)/sizeof(it); ++i)
	{
		if (n % primaries[i] == 0)
		{
			int a = n/primaries[i];
			cout << a << " " << n-a;
			break;
		}
	}
	return 0;
}

Posted via ActualForum NNTP Server 1.5

Dimitry Sibiryakov,спасибо.
1.Сюда запихнуть простые числа?

const int primaries[] = {2,3,5,7,11,13,...};

2.Что такое it?

for (int i = 1; i <= sizeof(primaries)/sizeof(it); ++i)

ванмомас намбаван
Что такое it?

int :)

Но думаю что для чисел порядка 10^9, int опасно использовать.
Лучше int64_t.

Преобразовал,на первом же тесте не верно.при вводе 10ти должно выдать две 5ки выдает 2 и 8.

#include <iostream>
#include <stdio.h>

using namespace std;



int main()
{
	const int primaries[] = { 2, 3, 5, 7, 11, 13,...};
	int n;
	cin >> n;
	if (n <= 1)
	{
		cout << "WTF?"
			return 1;
	}
	for (int i = 1; i <= sizeof(primaries) / sizeof(int); ++i)
	{
		if (n % primaries[i] == 0)
		{
			int a = n / primaries[i];
			cout << a << " " << n - a;
			break;
		}
	}
	return 0;
}

ванмомас намбаван
Преобразовал,на первом же тесте не верно.при вводе 10ти должно выдать две 5ки выдает 2 и 8.

А самостоятельно догадаться, что "it" - не единственная опечатка, а массивы нумеруются с
нуля?..

Posted via ActualForum NNTP Server 1.5

Dimitry Sibiryakov,ой не заметил,сорян

Какие то тесты программа умудряется просирать,не могу понять в чем траблы,на компе все пашит

#include <iostream>
#include <stdio.h>

using namespace std;



int main()
{
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	const long long int primaries[] = {2, 3, 5, 7, 11, 13,17,22,23};
	long long int n;
	cin >> n;
	
	for (long long int i = 0; i <= sizeof(primaries) / sizeof(long long int); ++i)
	{
		if (n % primaries[i] == 0)
		{
			long long int a = n / primaries[i];
			cout << n-a << " " << a;
			break;
		}
	}
	
	return 0;
}

С какого перепою у тебя 22 попало в список простых?

Posted via ActualForum NNTP Server 1.5