Проект Ойлер 234

Проект Ойлер е много готин сайт за тренировка на ума.

Съдържа няколкостотин задачи, които потенциално могат да се решат от умен човек с химикал и тетрадка, но са предназначени да бъдат решавани от умен човек с химикал, тетрадка и компютър.

Първите 50 се правят толкова бързо, колкото можеш да тракаш по клавиатурата. После става малко по-трудно.

Перфектното място за упражнение на нов език, както и за припомняне на стар.

Аз съм потребител x10.

234

Отговорът е 12591##43857##27161. Йей :)
Идеята е да се разгледа интервала $(p(x)^2, p(x+1)^2)$ където p(x) е x-тото просто число(отворени интервали, бтв). Това се прави за всяко x дотогава, докато $p(x)^2 < MAX$. В задачата MAX е съответно 15, 1000, 999966663333.

За всеки от тези интервали трябва да се намери колко числа в него се делят точно на едно от двете: p(x), p(x+1). Това нещо може да стане и за O(1) време, но с малко елементарна математика и здрав разум може да се докаже, че през целия живот на програмата, в тази част ще се разгледат не повече от $O(\sqrt{MAX})$ на брой числа - в случая, около триста хиляди пъти. С други думи, за да се изпълни така ще ти трябват няколко секунди. За да се напише по-добре - няколко минути.

Освен това - Project Euler е още едно място, което ми напомня защо вече не харесвам C++.

Когато задачата реално изисква мислене, по-хубаво е инструментите, които ползваш, да са част от решението, а не от проблема.

Дооста време писах решение на C++, което в крайна сметка не работеше. Дали е вярно или не - никога няма да разбера.
Първо, че не беше с оптималния алгоритъм (Оптимален алгоритъм на произволен език - секунда. Моят алгоритъм на Питон - 10-тина секунди. Тъп алгоритъм на C++ - 30 минути. Образователно.)
Второ, че въобще не изкарваше правилното число. Та нали int помни само 32 бита? А отговорът е с 19 цифри…
На всичкото отгоре стана към 3 пъти по-дълго… Защо да мога да напиша int n = 999966663333;, когато е толкова по-забавно да напиша int n = 99996666; n = n*1000 + 3333;
Защо пък в езика да няма 6 (на първоначален оглед, поне) вида числа? Естествено, че когато пиша функция за работа с числа трябва да внимавам точно за кой тип числа я пиша. Та нали ако не се занимавам с най-тъпите детайли, ще ми остане време реално да помисля над задачата? А кой би искал това…

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License