Про то, что будет, если P=NP. Доказательство может быть неконструктивным или алгоритм может быть настолько сложным, что для задач, встречающихся на практике, он будет непрактичен. Из P=NP следует только возможность данных новостей.
Нет. В оригинале «His paper shows that there is some number N smaller than 70 million such that there are infinitely many pairs of primes that differ by N.», что означает, что существует N<70,000,000, что есть бесконечно много пар простых с разностью N.
Только сжать в 2 раза не получится. Простые числа — очень сложно ведущая себя последовательность, взять хотя бы расширенную гипотезу Римана. (Исходя из неё эта сумма будет порядка N^2/(2*ln(n)) и там будет достаточно случайный член порядка N^3/2, т.е. сжать можно максимум на 25%).
(или www.google.com/settings/products, мой службы->изменить.)
easy:
www.spoj.com/problems/TDPRIMES/
www.spoj.com/problems/TDKPRIME/
hard:
www.spoj.com/problems/PRIMES2/
www.spoj.com/problems/KPRIMES2/
Учтите, там Pentium 3, в 8 раз медленнее моего Core 2 Duo. Мои решения hard задач работают ~3 раза быстрее TL.
Кто заинтересовался, советую почитать:
code.google.com/p/primesieve/
S(N)-N^2*x*(1+1/(1-x))/4
, гдеx=1/ln(N)
.n=2
ответ2
, у тебя0
. Ещё SIGSEGV приn = 1<<30
.N
, аn
. Я ещё отправил правильную версию по почте)N
, аn
.