программа, которая проверяет, является ли любое четное число больше 4 суммой двух простых чисел - PullRequest
Новая
       23

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

2 голосов
/ 01 апреля 2012

У меня следующая проблема:
Учитывая, что четные числа больше 4 могут быть получены путем сложения 2 простых числа, я должен написать алгоритм, который проверяет это. Алгоритм должен занимать меньше времени, чем O (n ^ 2).

Например, есть набор чисел от 6 до n. Если у нас есть число 6, ответ будет 6 = 3 + 3, а для 22 = 17 + 5 и т. Д.

Моя первая идея: 

S - set of n numbers
for i=1 to n {
  //removing odd numbers
   if (S[i]%2!=0)
      continue;

   result = false;
   for j=2 to S[i]-2{
       if (j.isPrime) // prime test can be done in O(log^2(n))
          if ((S[i]-j).isPrime)
               result = true;
               break;
          else
               continue;
   }

   if (result == false)
       break;
}

Поскольку я использую 2 цикла for, общее время выполнения этого алгоритма должно быть O(n*n)*O(log^2(n)) = O(n^2*log^2(n)), что не менее O(n^2). У кого-нибудь есть идея сократить время работы, чтобы получить требуемое время меньше O(n^2)?

Ответы [ 3 ]

2 голосов
/ 01 апреля 2012

Если набор содержит большие числа, у меня ничего нет.

Если max (S)

Вы должны предварительно обработать, какие числа из интервала [1, max (S)] являются простыми числами. Для предварительной обработки вы можете использовать Сито Эратосфена

Затем вы можете проверить, является ли число простым числом в O (1), и сложность вашего решения становится O (N ^ 2).

1 голос
/ 02 апреля 2012

Это гипотеза Гольдбаха .Известно, что тестирование на первичность выполняется в P (полиномиальное время), но безубыточность смехотворно высока - на практике вы не сможете сделать это где-нибудь вблизи O (n ^ 2)) .

Если мы предполагаем, что вам нужно иметь дело только с относительно небольшими числами, и вы можете предварительно вычислить простые числа до определенного предела, вам все равно нужно найти пары-кандидаты.Функция подсчета простых чисел дает примерно:
n / ln(n) простых чисел, меньше чем (n).Вычитание простого кандидата (p) из (n) дает нечетное число (q).Если вы можете найти простоту (q) со сложностью: n.ln(n) или лучше - то есть O (1) таблица поиска для всех нечетных чисел, меньших чемпредел - вы можете достичь O (n ^ 2) или лучше.

0 голосов
/ 01 апреля 2012

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

также взгляните на следующий вопрос - Программа для поиска простых чисел

...