Почала розв'язувати задачі с сайту projecteuler.net
Компілюю GCC. Використовую с++ 11.:)
Одразу ж і рахую час виконання коду.
Задача №1
If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
Find the sum of all the multiples of 3 or 5 below 1000.
Якщо ми перерахуємо усі числа до 10, які кратні 3 и 5, отримаємо 3, 5, 6 та 9. Сума цих дільників - 23.
Знайдіть сумму усіх чисел, що кратні 3 та 5 до 1000.
Моє рішення
▼Прихований текст
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <chrono>
int solve(int below)
{
int sum = 0;
for (int i = 1; i < below; ++i)
if (i % 3 == 0 || i % 5 == 0) sum += i;
return sum;
}
int main()
{
assert(solve(10) == 23);
auto now = std::chrono::high_resolution_clock::now();
auto answer = solve(1000);
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - now);
std::cout << "Answer = " << answer << "\n";
std::cout << "Time : " << elapsed.count() << "ns.\n";
return 0;
}
Задача №2
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
Рассматривая те элементы последовательности Фибоначчи, значение которых не превышает 4 миллиона, найти сумму всех положительных значений элементов.
Кожний новий елемент послідовності Фібоначчі генеруєтся сумою двох попередніх елементів. Починаючи з 1 і 2, перші десять елементів будуть - 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Розглядаючи ті елементи послідовності, значення котрих не перебільшує 4 мільйони, знайти суму усіх позитивних значень елементів.
Моє рішення
▼Прихований текст
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <chrono>
#include <vector>
long int solve(long int below)
{
int prev = 1;
int res = 2;
long int sum = 0;
while(res <= below)
{
if (res % 2 == 0) sum+= res;
int c = prev;
prev = res;
res = c + res;
}
return sum;
}
int main()
{
auto now = std::chrono::high_resolution_clock::now();
auto answer = solve(4000000);
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - now);
std::cout << "Answer = " << answer << "\n";
std::cout << "Time : " << elapsed.count() << "ns.\n";
return 0;
}
Задача №3
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Прості дільники числа 13195 є 5, 7, 13 та 29.
Який найбільший простий дільник у числа 600851475143?
Моє рішення
▼Прихований текст
#include <iostream>
#include <cstdlib>
#include <chrono>
#include <vector>
#include <cassert>
bool is_prime(unsigned long long num)
{
for (unsigned long long i = 2; i < num; ++i)
if(num % i == 0) return false;
return true;
}
unsigned long long solve(unsigned long long below_value)
{
int p = 2;
for (int i = 2; i < below_value; ++i)
if (below_value % i == 0 && is_prime(below_value / i)) return below_value/i;
}
int main()
{
assert(solve(10) == 5);
auto now = std::chrono::high_resolution_clock::now();
auto answer = solve(600851475143);
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - now);
std::cout << "Answer = " << answer << "\n";
std::cout << "Time : " << elapsed.count() << "ns.\n";
return 0;
}
Задача №4
A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.
Find the largest palindrome made from the product of two 3-digit numbers.
Паліндроми читаються однаково в обох напрямках. Найбільший паліндром, який можна отримати від добутку двух двозначних чисел - 9009 = 91 × 99. Знайти найбільший паліндром, який можна отримати добутком трьохзначних чисел.
Моє рішення
▼Прихований текст
#include <iostream>
#include <chrono>
#include <cassert>
#include <algorithm>
bool is_palindrom(long int num)
{
int b = 0;
int a = num;
while(num != 0)
{
b = b * 10 + num % 10;
num /= 10;
}
if (a == b)
return true;
return false;
}
int solve(int count_of_digits)
{
std::cout << count_of_digits << std::endl;
int start = 0, end = 0;
if (count_of_digits == 2) { start = 10; end = 99; }
if (count_of_digits == 3) { start = 100; end = 999; }
std::cout << start << std::endl;
std::cout << end << std::endl;
int mod = 0;
int max = 0;
for (int i = start; i <= end; ++i)
{
for(int j = start; j <= end; ++j)
{
mod = i*j;
if (is_palindrom(mod))
{
if (mod > max) max = mod;
}
}
}
return max;
}
int main()
{
auto result = solve(2);
assert(result == 9009);
auto now = std::chrono::high_resolution_clock::now();
auto answer = solve(3);
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - now);
std::cout << "Answer = " << answer << "\n";
std::cout << "Time : " << elapsed.count() << "ns.\n";
return 0;
}
Задача №5
2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
2520 - найменше число, яке ділиться на всі числа від 1 до 10 без останку. Яке найменше число ділиться без останку на всі числа від 1 до 20?
Моє рішення
▼Прихований текст
#include <iostream>
#include <chrono>
#include <cassert>
#include <algorithm>
bool check_divide(int in, int below_value)
{
for (int i = 1; i < below_value; ++i)
if (in % i != 0) return false;
return true;
}
int solve(const int below_value)
{
int i = 0;
bool fl = false;
while(!fl)
{
++i;
fl = check_divide(i, below_value);
}
return i;
}
int main()
{
auto result = solve(10);
assert(result == 2520);
auto now = std::chrono::high_resolution_clock::now();
auto answer = solve(20);
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - now);
std::cout << "Answer = " << answer << "\n";
std::cout << "Time : " << elapsed.count() << "ns.\n";
return 0;
}
Задача №6
The sum of the squares of the first ten natural numbers is,
12 + 22 + ... + 102 = 385
The square of the sum of the first ten natural numbers is,
(1 + 2 + ... + 10)2 = 552 = 3025
Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.
Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.
Сума квадратів перших десяти натуральних чисел
12 + 22 + ... + 102 = 385
Квадрат суми перших десяти натуральних чисел
(1 + 2 + ... + 10)2 = 552 = 3025
Отже різница між сумою квадратів перших десяти чисел та квадратом суми є 3025 − 385 = 2640. Знайти різницю між сумою квадратів перших десяти чисел та квадратом суми перших ста чисел.
Моє рішення
▼Прихований текст
#include <iostream>
#include <chrono>
#include <cassert>
#include <algorithm>
int sum_of_squares(int num)
{
int sum = 0;
for (int i = 1; i <= num; ++i)
sum += i*i;
return sum;
}
int square_of_sum(int num)
{
int sum = 0;
for(int i = 1; i <= num; ++i)
sum += i;
return sum*sum;
}
int solve(const int below_value)
{
return square_of_sum(below_value) - sum_of_squares(below_value);
}
int main()
{
auto result = solve(10);
assert(result == 2640);
auto now = std::chrono::high_resolution_clock::now();
auto answer = solve(100);
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::high_resolution_clock::now() - now);
std::cout << "Answer = " << answer << "\n";
std::cout << "Time : " << elapsed.count() << "ns.\n";
return 0;
}
