Пока мы не набрали n простых чисел, будем перебирать числа от 2 до ... и пытаться разложить их на множители.
Код вложен в ответ.
Решето Эратосфена позволяет быстро находить все простые числа на отрезке (в нашем случае x - какая-то константа).
АлгоритмПусть x равен 25.
Тогда идея такова: запишем все числа от 2 до 25.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
По умолчанию все числа помечены как простые. Конкретно здесь числа, помеченные как составные, будут показываться в нижних индексах: ₂₅
Берем первое число 2. Оно помечено как простое. От квадрата этого числа до x помечаем все числа, делящиеся на 2, как составные:
2 3 ₄ 5 ₆ 7 ₈ 9 ₁₀ 11 ₁₂ 13 ₁₄ 15 ₁₆ 17 ₁₈ 19 ₂₀ 21 ₂₂ 23 ₂₄ 25
Берем следующее число, помеченное как простое. Это 3. От квадрата этого числа до x помечаем все числа, делящиеся на 3, как составные:
2 3 ₄ 5 ₆ 7 ₈ ₉ ₁₀ 11 ₁₂ 13 ₁₄ ₁₅ ₁₆ 17 ₁₈ 19 ₂₀ ₂₁ ₂₂ 23 ₂₄ 25
Следующее простое число - 5. От квадрата пяти до x помечаем все числа, кратные 5, как составные:
2 3 ₄ 5 ₆ 7 ₈ ₉ ₁₀ 11 ₁₂ 13 ₁₄ ₁₅ ₁₆ 17 ₁₈ 19 ₂₀ ₂₁ ₂₂ 23 ₂₄ ₂₅
Квадрат всех остальных простых чисел больше x. Решето построено.
КодПеревернем массив, представляющий решето. В composite[i] хранится true, если i - составное, false иначе.
#include <bits/stdc++.h>
using namespace std;
const int x = 2000000;
bool composite[x + 1];
void calc() {
for (long long i = 2; i <= x; ++i)
if (!composite[i] && (i * i <= x))
for (long long j = i * i; j <= x; j += i)
composite[j] = true;
}
int main() {
calc();
int n;
cin >> n;
int k = 0;
for (int i = 2; i <= x && k < n; ++i)
if (!composite[i]) {
cout << i << " ";
++k;
}
cout << endl;
return 0;
}
ответ: Всего из букв С, Р, Е, Д, А можно составить 66 комбинаций
Объяснение:
Гласная + согласная + согласная - 12 вариантов:
ЕСР, ЕСД, ЕРС, ЕДС, ЕРД, ЕДР, АСР, АСД, АРС, АДС, АРД, АДР.
Гласная + согласная + гласная - 12 вариантов:
ЕСЕ, ЕРЕ, ЕДЕ, АСА, АРС, АДА, ЕСА, ЕРА, ЕДА, АСЕ, АРЕ, АДЕ.
Согласная + согласная + согласная - 12 вариантов:
СРС, СДС, РСР, РДР, ДСД, ДРД, СРД, СДР, РСД, РДС, ДСР, ДРС.
Согласная + гласная + согласная - 18 вариантов:
СЕС, САС, РЕР, РАР, ДЕД, ДАД, СЕР, СЕД, САР, САД, РЕС, РЕД, РАС, РАС, ДЕС, ДЕР, ДАС, ДАР.
Согласная + согласная + гласная - 12 вариантов:
СРЕ, СРА, СДЕ, СДА, РСЕ, РДЕ, РСА, РДА, ДСЕ, ДРЕ, ДСА, ДРА.
Подсчитаем общее количество вариантов:
12 + 12 + 12 + 18 + 12 = 66
ИЛИ
Гласная + согласная + согласная:
2 * 3 * 2 = 12
Гласная + согласная + гласная:
2 * 3 * 2 = 12
Согласная + согласная + согласная:
3 * 2 * 2 = 12
Согласная + гласная + согласная:
3 * 2 * 3 = 18
Согласная + согласная + гласная:
3 * 2 * 2 = 12
Подсчитаем общее количество вариантов:
12 + 12 + 12 + 18 + 12 = 66
Поделитесь своими знаниями, ответьте на вопрос:
Дано натуральное число n. Можно его представить в виде суммы трех квадратов натуральных чисел? Если можно то укажите тройку x, y, z таких натуральных чисел, что х* х + у* у + z*z =n; Напишите в виде блок-схемы
flag = 0;
for(x=1; x*x < n; x++) {
if (flag) break;
for(y=x; y*y < n; y++) {
if (flag) break;
for(z=y; z*z<n; z++) {
if (flag) break;
if (x*x+y*y+z*z == n) {
printf("x=%d y=%d z=%d\n", x, y, z);
flag = 1;
}
}
}
}
if (flag==0) printf("No\n");
Объяснение:
Без потери общности можно считать, что x <= y <= z