[c++] Простые гири

[Sla]

а почему ты начинаешь считать от максимального числа?
Ни в ТЗ, ни в логике этого не видно. Тебе так захотелось?

[Джон]

Хе? Не понял? Ты о чём?

Вводится некое число N (максимум 500 000) - от него я и начинаю считать.

Имеются гири с массами: 1 г, 2 г, ..., N г (N≤500000).

Входные данные
Входной файл INPUT.TXT содержит число N.

В моём примере N=100. Или?

[Sla]

N=100
максимальная сумма <= 100+100-2

ты начинаешь перебор гирь от 99. Почему?

[Джон]

Ха, прикол. Паскалевская прожка по линку даёт для N=100 49 пар

1  100
2  99
3  98
4  97
5  96
6  95
7  94
8  93
9  92
10  91
11  90
12  89
13  88
14  87
15  86
16  85
17  84
18  83
19  82
20  81
21  80
22  79
23  78
24  77
25  76
26  75
27  74
28  73
29  72
30  71
31  70
32  69
33  68
34  67
35  66
36  65
37  64
38  63
39  62
40  61
41  60
42  59
43  58
44  57
45  56
46  55
47  54
48  53
49  52

Хотя может быть я неправильно Паскаль в С++ перевёл. Я уже чёт забыл с ихними циклами

for i := n - 1 downto (n + 1) div 2 do
for i := 2 to trunc(sqrt(n)) do

условие окончания цикла строгое или нет? Я сделал строгое.

[Джон]

N=100
максимальная сумма <= 100+100-2

ты начинаешь перебор гирь от 99. Почему?

Где я начинаю перебор гирь от 99?

Смотри, у меня всего 100 гирь: 1, 2, 3, ... 100

1. Я нахожу наибольшее простое число на этом интервале - это 97.
2. 97 соостоит РОВНО из (97-1)/2=48 пар ВСЕХ чисел до него.
3. Остаётся остаток из четырёх гирь.

Кстати паскалевская пржка делает тчно также, но только в том случае если N изначально простое.

[Sla]

Джон, блин!!!
99+97 - это максимальная сумма двух гирь!!!

[Джон]

96   +   1   =   97
95   +   2   =   97
94   +   3   =   97
93   +   4   =   97
92   +   5   =   97
91   +   6   =   97
90   +   7   =   97
89   +   8   =   97
88   +   9   =   97
87   +   10   =   97
86   +   11   =   97
85   +   12   =   97
84   +   13   =   97
83   +   14   =   97
82   +   15   =   97
81   +   16   =   97
80   +   17   =   97
79   +   18   =   97
78   +   19   =   97
77   +   20   =   97
76   +   21   =   97
75   +   22   =   97
74   +   23   =   97
73   +   24   =   97
72   +   25   =   97
71   +   26   =   97
70   +   27   =   97
69   +   28   =   97
68   +   29   =   97
67   +   30   =   97
66   +   31   =   97
65   +   32   =   97
64   +   33   =   97
63   +   34   =   97
62   +   35   =   97
61   +   36   =   97
60   +   37   =   97
59   +   38   =   97
58   +   39   =   97
57   +   40   =   97
56   +   41   =   97
55   +   42   =   97
54   +   43   =   97
53   +   44   =   97
52   +   45   =   97
51   +   46   =   97
50   +   47   =   97
49   +   48   =   97

[Sla]

а что такое "строгое" окончание  цикла?

[Sla]

Джон, да отвяжись ты от простых чисел!!!

[Джон]

Джон, блин!!!
99+97 - это максимальная сумма двух гирь!!!

Хе? Ты сейчас о чём? При чём здесь максимальная сумма двух гирь (хотя смысла этого выражения я не пнимаю - разве у двух гирь может быть несколько сумм? максимальная и немаксимальная? )? Ну может быть. Ну и что? Это не важно. Я перебрал все гири и у меня осталось только четыре.

97
98
99
100

Из них я могу получить ещё две пары в сумме дающие простые числа. Таким образом я получаю (конечно аналитически) теоретически максимально возможное число пар - 50.

[Джон]

а что такое "строгое" окончание  цикла?

i<n  vs  i<=n

[Джон]

Джон, да отвяжись ты от простых чисел!!!

Почему? Это же условие, сумма двух гирь должна быть простым числом.

[Sla]

я говорю о том, что 99+98 может быть простым число и входить во множество по 2 из ста.

[Джон]

"Меня терзают смутные сомнения" (с)

Похоже мы с тобой о разных вещах говорим. Что значит "множество по 2 из 100"? Что эта пара должна учитываться? Конечно, я же написал:

Для очистки совести:

97 +  98 = 195
99 + 100 = PRIME 199 +1

97 + 100 = PRIME 197
98 + 99   = PRIME 197

Первая комбинация даёт только одну пару, вторая - две.

[Джон]

Ну короче всё прояснилось. Это я накосячил - неправильно циклы перевёл, проверка условия нестрогая. Получается ровно 50. Там как раз пары 50 и 51 не хватает. Собственно это и навело на ошибку.

А жаль.

[Джон]

Код выложить?

[Sla]

та показуй

[Джон]

Вариант когда N=2 я не стал обрабатывать, это и так понятно:

Код:

BOOL CPrimeNumberDlg::Easy(long n)
{
	for(long i=2; i<=(int)(sqrt((double)n)); i++)
	{
		if((n%i)==0)
		{
			return FALSE;
		}
	}
	return TRUE;
}

long CPrimeNumberDlg::FindEasy(long n)
{
	for(long i=n+1; i<=999999; i++)
	{
		if(Easy(i))
		{
			return i;
		}
	}
	return 0;
}

void CPrimeNumberDlg::OnBnClickedButton2()
{
	UpdateData(TRUE);

	int nPairCnt = 0;

	int n = m_nMax;

	if(Easy(n))
	{
		for(long i=n-1; i>=(n+1)/2; i--)
		{
			TRACE("%d\t%d\n", i, n-i);
			nPairCnt++;
		}
	}
	else
	{
		long m = 0;
		while(n>0)
		{
			m = FindEasy(n);
			if( (m==0) || (m>=2*n) )
			{
				break;
			}

			for(long i = m- n; i<=m/2; i++)
			{
				TRACE("%d\t%d\n", i, m-i);
				nPairCnt++;
			}
			n = m - n - 1;
		}
	}

	TRACE1("Pairs: %d\n", nPairCnt);
}

[Джон]

Код подправил. Во вспомогательных ф-ях циклы for, а то получалось что 15 тоже простое число.

Вот проект (MFC VS .NET 2003), если кто захочет поиграться.