e-olymp 4739. Решето Эратосфена

08/12/2020 by Oleksandr.Ivanov

Задача

По заданным числам $a$ и $b$ вывести все простые числа в интервале от $a$ до $b$ включительно.

Входные данные

Два числа $a$ и $b \ (1 \leqslant a \leqslant b \leqslant 100000)$.

Выходные данные

Вывести в одной строке все простые числа в интервале от $a$ до $b$ включительно.

Тесты

№	Входные данные	Выходные данные	Объяснение
1	2 2	2
2	1 100	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
3	50 100	53 59 61 67 71 73 79 83 89 97
4	10 2		Неправильно, так как противоречит условию ($a \leqslant b$)
5	99900 100000	99901 99907 99923 99929 99961 99971 99989 99991
6	-15 -6	-13 -11 -7	Неправильно, так как противоречит условию ($1 \leqslant a \leqslant b \leqslant 100000$)

Код

#include <iostream>
#include <cmath>

using namespace std;


bool eratosthenesSieve(int currentNumber) {
    /*
    Describe the function that checks if the number is prime and returns a boolean value.
    This function is based on the "sieve of Eratosthenes" algorithm.
    True - if the number is prime, false - normal.
    */
    
    // If the number equals to 1 or if it even, return false. And if it equals to 2, return true.
    if (currentNumber == 2 or currentNumber == 3) {
        return true;
    } else if (!(currentNumber % 2) or !(currentNumber % 3) or currentNumber == 1) {
        return false;
    }
    
    // If the number has the divider from 5 to the root of this number with the second step return false.
    for (int divider = 5; divider <= sqrt(currentNumber); divider += 2) {
        if (!(currentNumber % divider)) {
            return false;
        }
    }
    
    // In all other situations, return true.
    return true;
}


void printSequenceOfPrimeNumbers(int beginning, int ending) {
    /*
    This function prints all prime numbers in a line.
    It contains a loop that starts and ends with the given values.
    */

    for (int sequenceElement = beginning; sequenceElement <= ending; sequenceElement += 1) {
        if (eratosthenesSieve(sequenceElement)) {
            cout << sequenceElement << " ";
        }
    }
}


int main() {
    /*
    Receive the beginning and end of the sequence.
    */
    
    int beginning, ending;
    cin >> beginning >> ending;
    
    // Calling the function.
    printSequenceOfPrimeNumbers(beginning, ending);

    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

bool eratosthenesSieve(int currentNumber) {

Describe the function that checks if the number is prime and returns a boolean value.

This function is based on the "sieve of Eratosthenes" algorithm.

True - if the number is prime, false - normal.

// If the number equals to 1 or if it even, return false. And if it equals to 2, return true.

if (currentNumber == 2 or currentNumber == 3) {

return true;

} else if (!(currentNumber % 2) or !(currentNumber % 3) or currentNumber == 1) {

return false;

}

// If the number has the divider from 5 to the root of this number with the second step return false.

for (int divider = 5; divider <= sqrt(currentNumber); divider += 2) {

if (!(currentNumber % divider)) {

return false;

}

// In all other situations, return true.

return true;

}

void printSequenceOfPrimeNumbers(int beginning, int ending) {

This function prints all prime numbers in a line.

It contains a loop that starts and ends with the given values.

for (int sequenceElement = beginning; sequenceElement <= ending; sequenceElement += 1) {

if (eratosthenesSieve(sequenceElement)) {

cout << sequenceElement << " ";

}

int main() {

Receive the beginning and end of the sequence.

int beginning, ending;

cin >> beginning >> ending;

// Calling the function.

printSequenceOfPrimeNumbers(beginning, ending);

return 0;

}

Решение

Решето Эратосфена это алгоритм поиска простых чисел.
Решение данной задачи сводится к тому, чтобы воплотить данный алгоритм. По мере прохождения перечня, нужные числа остаются, а ненужные (составные) исключаются.

Это решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых.

Рассуждение:
— Все четные числа, не считая двойки, — составные, то есть не являются простыми, так как делятся не только на себя и единицу, а также еще на $2$.
— Все числа кратные трем, кроме самой тройки, — составные, так как делятся не только на самих себя и единицу, а также еще на $3$.
— Число $4$ уже выбыло из игры, так как делится на $2$.
— Число $5$ простое, так как его не делит ни один простой делитель, стоящий до него.
— Если число не делится ни на одно простое число, стоящее до него, значит оно не будет делиться ни на одно сложное число, стоящее до него.

В моем коде, указанном выше, была реализована функция-фильтр, которая, по большей части, реализовывает метод перебора делителей и проверяет: есть ли делители числа, кроме его самого, вплоть до корня из этого числа. И если остатки от деления не равны $0$, то мы возвращаем истину, что означает: число простое.

Таким же образом, проверяем все остальные числа из промежутка от $n$ до $m$ и выводим полученную последовательность на экран.

Ссылки

Related Images:

e-olymp 94. Problem of prime numbers!

10/01/2019 by Руслан Масальский

The task is taken from e-olymp

Task

One of the most difficulties of an instructor is question design for the final-term exam. Dr. Ghavamnia teaches “Fundamentals of Algorithms” at University of Isfahan (UI) and has designed a good practical algorithmic problem for his exam. He wants that students use all of their algorithmic skills to code this problem as best and efficient as they can. The problem is as follows: a ring is composed of [latex]N[/latex] circles numbered from [latex]1[/latex] to [latex]N[/latex] as shown in diagram. You are given [latex]N[/latex] integer numbers. Put these numbers into each circle separately with the condition that sum of numbers in three adjacent circles must be a prime.
Each test case may have several solutions and your task is to find the one with minimum weighted sum. Weighted sum is defined as the sum of products of each number in circle by the sequence number of that circle. For instance, the weighted sum in above diagram is [latex]36[/latex] (and also it is the minimum).

Input

The first line of input contains a single integer, the number of test cases. Following, there is one line for each test case. Each test case begins with one integer, [latex]N[/latex] ([latex]3 \leq N \leq 15[/latex]), which is the number of circles. Next [latex]N[/latex] integers are the given numbers to put in circles (all between [latex]1[/latex] and [latex]100[/latex], inclusively).

Output

There should be one line for each test case in output. If there’s no way for building the ring, the word «impossible» should be outputted, or otherwise, a single integer which is the minimum weighted sum.

Tests

№	Inputs	Outputs
1	5 4 1 3 7 9 4 1 1 3 5 15 11 6 2 3 2 14 1 2 10 7 2 2 3 6 2 9 1 1 1 2 2 2 2 2 2 7 1 2 3 4 5 6 7	36 imposible 396 72 imposible

Code

#include <iostream>
#include <vector> 
#include <string>
using namespace std;
int length;
vector <int> input(16);
vector <int> output(16);
bool used[16];
const int SIZE = 350;
bool isPrime[SIZE];
const int INF = 2147483647;
long min;
bool prime(int k) {
    return isPrime[k];
}
void init() { // initialization for Sieve of Eratosthenes
    for (int i = 0; i < SIZE; i++) {
        isPrime[i] = true;
    }
    for (int i = 2; i * i < SIZE; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < SIZE; j += i) {
                isPrime[j] = false;
            }
        }
    }
}
void perm(int pos) {
    if (pos == length) {
        if (!prime(output[pos - 1] + output[0] + output[1]) || !prime(output[pos - 1] + output[pos - 2] + output[0])) {
            return;
        }
        for (int z = 0; z < length; z++) {
            long temp = 0;
            for (int i = 1; i <= length; i++) {
                temp += i * output[i - 1];
            }
            if (temp < ::min) {
                ::min = temp;
            }
            int k = output[0];
            for (int j = 0; j < length - 1; j++) {
                output[j] = output[j + 1];
            }
            output[length - 1] = k;
        }
        return;
    }
    for (int i = 0; i < length; i++)
        if (!used[i]) {
            output[pos] = input[i];
            if (pos >= 2 && !prime(output[pos] + output[pos - 1] + output[pos - 2])) {
                continue;
            }
            used[i] = true;
            perm(pos + 1);
            used[i] = false;
        }
}
int main() {
    string f;
    init();
    int t;
    cin >> t;
    for (int j = 0; j < t; j++) {::min = INF;
        scanf("%d", &length);
        for (int i = 0; i < length; i++) {
            scanf("%d", &(input[i]));
        }
        output[0] = input[0];
        used[0] = true;
        perm(1);
        f = (::min == INF ? "impossible" : to_string(::min));
        printf("%s\n", f.c_str());
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <string>

using namespace std;

int length;

vector <int> input(16);

vector <int> output(16);

bool used[16];

const int SIZE = 350;

bool isPrime[SIZE];

const int INF = 2147483647;

long min;

bool prime(int k) {

return isPrime[k];

}

void init() { // initialization for Sieve of Eratosthenes

for (int i = 0; i < SIZE; i++) {

isPrime[i] = true;

}

for (int i = 2; i * i < SIZE; i++) {

if (isPrime[i]) {

for (int j = i * i; j < SIZE; j += i) {

isPrime[j] = false;

}

void perm(int pos) {

if (pos == length) {

if (!prime(output[pos - 1] + output[0] + output[1]) || !prime(output[pos - 1] + output[pos - 2] + output[0])) {

return;

}

for (int z = 0; z < length; z++) {

long temp = 0;

for (int i = 1; i <= length; i++) {

temp += i * output[i - 1];

}

if (temp < ::min) {

::min = temp;

}

int k = output[0];

for (int j = 0; j < length - 1; j++) {

output[j] = output[j + 1];

}

output[length - 1] = k;

}

return;

}

for (int i = 0; i < length; i++)

if (!used[i]) {

output[pos] = input[i];

if (pos >= 2 && !prime(output[pos] + output[pos - 1] + output[pos - 2])) {

continue;

}

used[i] = true;

perm(pos + 1);

used[i] = false;

}

int main() {

string f;

init();

int t;

cin >> t;

for (int j = 0; j < t; j++) {::min = INF;

scanf("%d", &length);

for (int i = 0; i < length; i++) {

scanf("%d", &(input[i]));

}

output[0] = input[0];

used[0] = true;

perm(1);

f = (::min == INF ? "impossible" : to_string(::min));

printf("%s\n", f.c_str());

}

return 0;

}

Solution

We need all permutations of our array and if permutation suits us update [latex]min[/latex] value. To check if number is prime I use Sieve of Eratosthenes. To get all permutation I use recursive function which works in this way:
We accumulate an array in all possible ways. What we do:

Fixed empty position in array with a value
Remember that we used this value
Find all permutations of array with size which is smaller by 1
Forget that we used this value (to use it in next permutations)

We stop when we accumulate an array with size we need and check if this permutation suits us(if sum of all triples of this circle are prime). If yes update answer(if it is less than answer). So if we send this solution to server we will get time limit. We need to reduce permutations which do not suit us. To speed up our program we can reduce amount of permutations in this way: if we find out that sum of previous three numbers, which are fixed, is not prime, we do not need to continue this branch of recursion. Really if in our array we found that one sum of three number is not prime we do not need to accumulate this array further. But anyway we get time limit.
Let’s see the differences in complete array where any some of three numbers is prime number.
Input: 8 2 1
Let’s find all suitable permutations:

8 2 1
2 8 1
2 1 8
1 8 2
8 1 2
1 2 8

As you can see first three are different with shifts. Last three are also different with shifts. So we can fix one element find all permutations we need with less by 1 amount of elements and then shift all elements of every array to get all possible permutations which are correct as you can see above (1,2,3) (4,5,6). In the worst case it will work not for [latex]15![/latex] but for [latex]14![/latex]. And now we get Accept.
The complexity is [latex]O(n!)[/latex] Why I did not get time limit at all (because of complexity)? In task said than amount of test which works with [latex]O(n!)[/latex] can be huge. But who will make so many tests? In our case there are near 5 tests in one.

e-olymp 8362. Множители

28/10/2018 by Инна Литвиненко

Задача

Найти число от $1$ до $n$ включительно такое, что в разложении его на простые множители количество множителей максимально. Если таких чисел несколько, выбрать максимальное из них.

Например, если $n = 7$, то ответом будет число $6$, как наибольшее число, имеющее в своем разложении $2$ простых множителя $2$ и $3$.

Входные данные

Одно целое число $n$ $(1 ≤ n ≤ 2^{31}- 1)$.

Выходные данные

Вывести одно искомое число.

Тесты

№	Ввод	Вывод
1	1	1
2	10	8
3	100	96
4	363	256
5	2147483647	1610612736

Код программы с использованием цикла

#include <iostream>
using namespace std;

int main() {
    long long int n, a = 2, b = 3;
    cin >> n;
    if (n <= 3) cout << n;
    else {
        while (a * 2 <= n) a *= 2;
        while (b * 2 <= n) b *= 2;
        cout << max(a, b);
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long int n, a = 2, b = 3;

cin >> n;

if (n <= 3) cout << n;

else {

while (a * 2 <= n) a *= 2;

while (b * 2 <= n) b *= 2;

cout << max(a, b);

}

return 0;

}

Код программы с использованием условных операторов

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    long long n;
    cin >> n;
    if (n <= 3)
        cout << n;
    else {
        long long pow, a = 2, b = 3;
        pow = log(n) / log(2);
        a = a << (pow - 1);
        b = b << (pow - 1);
        if (a <= n && b <= n)
            cout << max(a, b);
        else if (a > n)
            cout << b;
        else
            cout << a;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

long long n;

cin >> n;

if (n <= 3)

cout << n;

else {

long long pow, a = 2, b = 3;

pow = log(n) / log(2);

a = a << (pow - 1);

b = b << (pow - 1);

if (a <= n && b <= n)

cout << max(a, b);

else if (a > n)

cout << b;

else

cout << a;

}

return 0;

}

Решение

Для решения данной задачи нам необходимо понять, что чем меньше простой множитель, тем больше таких множителей может содержать в себе искомое число, значит наше число состоит только из двоек или из двоек и одной тройки.

Заметим, что если заданное число будет единицей, двойкой или тройкой, то его и надо вывести на экран.

Условные операторы

Для начала с помощью логарифма найдем максимальный показатель степени двойки, содержащейся в заданном числе. Заметим, что нас интересует только целая часть полученного результата.

Далее возьмём двойку и тройку (как наименьшие возможные простые множители искомого числа) и сдвинем их битово влево на показатель степени двойки минус один, так как эта первая степень уже заложена в самих 2 и 3. Сдвигать нужно для того, чтоб повысить степень двойки в нашем числе, тем самым увеличив количество простых множителей.

Из двух полученных в результате наших действий чисел выберем наибольшее не превосходящее входные данные.

Цикл

Создадим две переменные равные двум и трём и будем увеличивать их вдвое до тех пор, пока полученное число не превосходит заданное.

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

Ссылки

Задача множители на e-olymp

Решение задачи на Ideone циклом

Решение задачи на Ideone условными операторами

Related Images:

e-olymp 3843. Простые

06/06/2018 by Илья Черноморец

Задача

Пусть $m$ и $n$ $\left(2 ≤ m < n ≤ 107\right)$ — целые числа. Рассмотрим следующее множество:

Prime $\left(m, n\right) = \lbrace{ p | p\;простое, m ≤ p ≤ n \rbrace}$.

Вычислить мощность множества Prime$\left(m, n\right)$.

Входные данные

Состоит из нескольких тестов. Два последовательных теста разделены пустой строкой. Для каждого теста в отдельной строке заданы числа $m$ и $n$.

Выходные данные

Для каждого теста вывести результат в отдельной строке. Результаты соседних тестов разделять пустой строкой. Для каждого теста вывести мощность множества Prime$\left(m, n\right)$.

Тесты

Входные данные	Выходные данные
2 20 70 110 5 150	8 10 33
7 2056 14 181 27 367	307 36 64
77 777 55 555 33 333	116 85 56

Входные данные

Выходные данные

2 20

70 110

5 150

7 2056

14 181

27 367

307

77 777

55 555

33 333

116

Код решения

#include <iostream>
#include <cmath>
using namespace std;


int main()
{
     int n, m;  
     const int MAXN = 10000001;
     bool simple[MAXN];
     for(int i = 2; i <= MAXN; i++){
         simple[i] = true;
     }
     for(int i = 2; i <= sqrt(MAXN); i++){
         if(simple[i]){
             for(int j = i * i; j <= MAXN; j += i){
                 simple[j] = false;
             }
         }
     }

     int count[MAXN];
     int lastSum = 0;
     for(int i = 1; i < MAXN; i++){
         count[i] = lastSum + simple[i];
         lastSum = count[i];
     }
     while(cin >> m >> n){
         int answer = count[n] - count[m] + simple[m];
         cout << answer << endl << endl;
     }
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int n, m;

const int MAXN = 10000001;

bool simple[MAXN];

for(int i = 2; i <= MAXN; i++){

simple[i] = true;

}

for(int i = 2; i <= sqrt(MAXN); i++){

if(simple[i]){

for(int j = i * i; j <= MAXN; j += i){

simple[j] = false;

}

int count[MAXN];

int lastSum = 0;

for(int i = 1; i < MAXN; i++){

count[i] = lastSum + simple[i];

lastSum = count[i];

}

while(cin >> m >> n){

int answer = count[n] - count[m] + simple[m];

cout << answer << endl << endl;

}

Решение

Для решения этой задачи требуется завести большой массив типа bool и присвоить ему значение true. Затем проверяется, простое ли число, если это не так, то присваиваем значение false.
Затем нужно последовательно сосчитать мощность каждого множества простых чисел, то есть количество простых чисел от n до m, с помощью массива-счётчика: записывается в него прошлые и последующие элементы множества простых чисел.
После этого в цикле задаются нужные значения, считается ответ и выводится.

Условие задачи на e-olymp.com
Код решения на ideone.com

Related Images:

e-olymp 520. Сумма всех

26/12/2017 by Даниил Крутоголов

Сумма всех

Вычислите сумму всех заданных чисел.

Входные данные

Содержит [latex]n[/latex] [latex] (1 ≤ n ≤ 10^5) [/latex] целых чисел. Все числа не превосходят [latex]10^9[/latex] по абсолютной величине.

Выходные данные

Выведите сумму всех заданных чисел.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]2[/latex] [latex]4[/latex]	[latex]6[/latex]
2	[latex]3[/latex]	[latex]3[/latex]
3	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex]	[latex]9[/latex]
4	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex]	[latex]10[/latex]
5	[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex]	[latex]0[/latex]

Код программы

#include <iostream>
 
using namespace std;
 
int main() {
    long x;
    long sum = 0;
    while (cin >> x){
        sum+= x;
    }
    cout << sum;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long x;

long sum = 0;

while (cin >> x){

sum+= x;

}

cout << sum;

return 0;

}

Решение задачи

Пользователь вводит числа до тех пор, пока программа не завершит работу. Как только это случается, программа выдаёт ответ в виде суммы всех ранее введённых чисел. Также, стоит использовать переменную типа long из-за того, что сумма чисел может быть довольно большой и явно превышать максимальное допустимое значение для переменной типа int.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

A 325. Простые делители числа

28/08/2017 by Курьянов Павел

Задача
Дано натуральное число [latex]n[/latex]. Получить все простые делители этого числа.

Входные данные
Натуральное число [latex]n[/latex]

Выходные данные
Все его простые делители напечатанные через пробел

Тесты

входные данные	выходные данные
2	2
7	7
50	2 5 5
169	13 13
583	11 53
2368	2 2 2 2 2 2 37
73890	2 3 3 5 821
885066	2 3 7 13 1621
6943960340	2 2 5 97 1787 2003

Код программы

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    unsigned long long n;
  cin>>n;
    
    for (unsigned long long i = 2; i < sqrt(n)+0.00001; )    {
        if ( n % i == 0 ){
            std::cout << i << ' ';
            n /= i;
        }
        else{
            ++i;
        }
    }
    if ( n > 1 )
        std::cout << n;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

unsigned long long n;

cin>>n;

for (unsigned long long i = 2; i < sqrt(n)+0.00001; ) {

if ( n % i == 0 ){

std::cout << i << ' ';

n /= i;

}

else{

++i;

}

if ( n > 1 )

std::cout << n;

return 0;

}

Решение задачи
Для решения задачи мы проверяем все числа от 2 до [latex]\sqrt{n}[/latex]. Если число является делителем [latex]n[/latex], то мы его выводим и делим [latex]n[/latex] на это число. Повторная проверка на простоту не требуется так как мы ведем поиск снизу, а значит число полученное после проверки уже не может делиться на составное. В конце, если остается простой делитель больше, то он выводиться так же.

Ссылки

Условие задачи(страница 135)
Код на ideone

Related Images:

A328

21/06/2017 by Алла Марокко

Задача:
Найти [latex]100[/latex] первых простых чисел.
Тесты:
Обобщим задачу и для тестов используем разное количество первых простых чисел.

№	Вход	Выход
1	25	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
2	50	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229
3	100	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541

Код:

#include <iostream>
using namespace std;

int main() { 
    printf("2"); 
    int n;
    cin>>n;
    for (int i=3; n; i+=2) { 
        for (int j = 3; j*j<=i ; ++j){
            if (i%j==0) goto next;
        }
        printf(", %d",i);
        --n; 
        next:;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

printf("2");

int n;

cin>>n;

for (int i=3; n; i+=2) {

for (int j = 3; j*j<=i ; ++j){

if (i%j==0) goto next;

}

printf(", %d",i);

--n;

next:;

}

return 0;

}

Решение:
Первое простое число печатаем сразу, остальные [latex]n-1[/latex] будем проверять циклами: проверим нечетные числа на нечетные делители(пройдём цикл по делителям). Число простое, если нет делителей. Если не простое, то переходим к следующему. Каждое простое число печатаем до [latex]n[/latex] включительно.
Ссылки:

Условие задачи.
Онлайн компилятор ideone.

Related Images:

e-olymp 1285. Деление Гольдбаха

10/06/2017 by Тимур Фирсов

Задача

Широко известна проблема Гольдбаха! Вот одна из её версий:

Любое нечетное число больше [latex]17[/latex] можно записать в виде суммы трёх нечётных простых чисел;
Любое чётное число больше [latex]6[/latex] можно записать в виде суммы двух нечётных простых чисел.

Если число чётное, то мы раскладываем его на суммы двух простых разных нечётных, а если нечётное — то на суммы трёх простых разных нечётных. Такой способ разложения для заданного [latex]N[/latex] назовём делением Гольдбаха и обозначим как [latex]G\left( N \right)[/latex].
Зная заданное число [latex]N[/latex], найти [latex]\left| G\left( N \right) \right| [/latex], т.е. количество различных [latex]G(N)[/latex].

Входные данные:

Входные данные содержат несколько тестовых случаев.
Каждый тест в отдельной строке содержит одно единственное число [latex]N \left( 1\le N\le 20000 \right) [/latex].
Ввод продолжается до конца входного файла.

Выходные данные:

Для каждого тестового случая вывести в отдельной строке одно число — найденное значение [latex]\left| G\left( N \right) \right| [/latex].

Тесты

№	Входные данные	Выходные данные
1	5 8 18 19 20	0 1 2 1 2
2	13 22 78 4 150	0 2 7 0 12
3	2000	37
4	6 8 17 19 337	0 1 0 1 195

Код программы

#include <iostream>
#include <vector>
#include <unordered_map>
#include <cmath>
using namespace std;

bool prime (int x){ //функция для проверки простоты нечётного числа
    bool pr=true;
    for(int i=2; i<=sqrt(x);i++)if(!(x%i))pr=false;
    return pr;
}
int main() {
    vector <int> v,prime_v;
    unordered_map <int,bool> prime_m;
    int u,i,j,maxx=0;
    while(cin>>u){
        v.push_back(u);
        maxx=max(maxx,u);//максимальное значение во входном потоке
    }
    for(i=3;i<=maxx;i+=2){
        if(prime(i)){
            prime_m[i]=true;
            prime_v.push_back(i); 
        }
    }
    int *dp,k;
    dp = new int [maxx+1];
    for(i=0;i<=maxx;i++)dp[i]=0;
    for(i=8;i<=maxx;i++){//заполняем массив значениями |G(i)|
        if(i%2){
            for(j=0;(j<prime_v.size())&&(prime_v[j]<i);j++){
                k=i-prime_v[j];
                if(dp[k]){
                    dp[i]+=dp[k];
                    if((prime_m[k-prime_v[j]])&&((k-prime_v[j])!=prime_v[j]))--dp[i];
                }
            }
        }
        else{
            for(j=0;(j<prime_v.size())&&(prime_v[j]<(i/2));j++){
                k=i-prime_v[j];
                if(prime_m[k])dp[i]++;
            }
        }
        if(i%2)dp[i]/=3;
    }
    for(i=0;i<v.size();i++)cout<<dp[v[i]]<<'\n';
    return 0;
}

#include <iostream>

#include <vector>

#include <unordered_map>

#include <cmath>

using namespace std;

bool prime (int x){ //функция для проверки простоты нечётного числа

bool pr=true;

for(int i=2; i<=sqrt(x);i++)if(!(x%i))pr=false;

return pr;

}

int main() {

vector <int> v,prime_v;

unordered_map <int,bool> prime_m;

int u,i,j,maxx=0;

while(cin>>u){

v.push_back(u);

maxx=max(maxx,u);//максимальное значение во входном потоке

}

for(i=3;i<=maxx;i+=2){

if(prime(i)){

prime_m[i]=true;

prime_v.push_back(i);

}

int *dp,k;

dp = new int [maxx+1];

for(i=0;i<=maxx;i++)dp[i]=0;

for(i=8;i<=maxx;i++){//заполняем массив значениями |G(i)|

if(i%2){

for(j=0;(j<prime_v.size())&&(prime_v[j]<i);j++){

k=i-prime_v[j];

if(dp[k]){

dp[i]+=dp[k];

if((prime_m[k-prime_v[j]])&&((k-prime_v[j])!=prime_v[j]))--dp[i];

}

else{

for(j=0;(j<prime_v.size())&&(prime_v[j]<(i/2));j++){

k=i-prime_v[j];

if(prime_m[k])dp[i]++;

}

if(i%2)dp[i]/=3;

}

for(i=0;i<v.size();i++)cout<<dp[v[i]]<<'\n';

return 0;

}

Засчитанное решение на e-olymp.com

Решение

Поместим все тестовые случаи в вектор и найдём максимальное из данных чисел — [latex]max[/latex]. Затем найдём все нечётные простые числа меньшие [latex]max[/latex] (единственное чётное простое число — [latex]2[/latex]). Заведём массив размером [latex]max+1[/latex], [latex]i[/latex]-м элементом которого будет [latex]\left| G\left( i \right) \right| [/latex]. Тогда, если [latex]i[/latex]- чётное, то одно из слагаемых суммы [latex]a_{i}+b_{i}[/latex] двух простых разных нечётных чисел будем подбирать из найденных ранее простых нечётных чисел, но строго меньших [latex]\frac { i }{ 2 } [/latex], чтобы разбиения, отличающиеся только порядком следования частей считать равными, и выполнялось неравенство [latex]a_{i}\neq b_{i}[/latex]. Если разность [latex]i[/latex] и подобранного таким образом числа — нечётное простое число, то это деление Гольдбаха, тогда увеличиваем на единицу [latex]\left| G\left( i \right) \right| [/latex]. Если [latex]i[/latex] — нечётное, то [latex]a_{i}[/latex]из суммы [latex]a_{i}+b_{i}+c_{i}[/latex] трёх простых разных нечётных чисел будем подбирать из всех простых нечётных чисел строго меньших [latex]i[/latex]. Разностью [latex]i[/latex] и подобранного числа [latex]a_{i}[/latex] (разность двух нечётных) будет чётное число [latex]j[/latex], [latex]\left| G\left( j \right) \right| [/latex] мы уже нашли ранее. Тогда можем представить [latex]\left| G\left( j \right) \right| [/latex] различных разложений [latex]G\left( i \right)[/latex] в виде [latex]a_{i}+G\left( j \right)_{k}[/latex] или [latex]a_{i}+{a_j}_{k}+{b_j}_{k}[/latex], где [latex]k=\overline { 1,\left| G\left( j \right) \right| } [/latex], a [latex]G\left( j \right)_{k}[/latex] — [latex]k[/latex]-е разбиение числа [latex]j[/latex]. Значит все полученные [latex]\left| G\left( j \right) \right| [/latex] будем прибавлять к [latex]\left| G\left( i \right) \right| [/latex], а чтоб избежать ситуаций [latex]a_i={a_j}_k[/latex] и [latex]a_i={b_j}_k[/latex], если [latex]i-2a_{i}[/latex] — простое число не равное [latex]a_{i}[/latex] (то есть при некотором значении [latex]k[/latex] одно из чисел [latex] G\left( j \right)_{k} [/latex] равно [latex]a_{i}[/latex] и не равно второму числу, так как [latex]{a_{j}}_k\neq {b_{j}}_k[/latex] мы учли ранее), то будем отнимать единицу от [latex]\left| G\left( i \right) \right| [/latex]. В разбиениях [latex]j[/latex] мы не учитываем порядок следования частей. Чтобы не учитывать его в и разбиениях числа [latex]i[/latex], разделим полученный результат [latex]\left| G\left( i \right) \right| [/latex] на [latex]3[/latex].

Ссылки

Related Images:

A327. Простые числа

13/11/2016 by Эммануил Прокопов

Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны натуральные числа [latex]a, b (a\le b)[/latex]. Получить все простые числа [latex]p[/latex], удовлетворяющие неравенствам [latex]a\le p\le b[/latex].

Входные данные:
Два натуральных числа [latex]a[/latex] и [latex]b[/latex].

Выходные данные:
Некоторое количество натуральных чисел.

Тесты.

№	Входные данные		Выходные данные
	[latex]a[/latex]	[latex]b[/latex]	[latex]p[/latex]
1	1	4	2, 3
2	0	1	Not found
3	5	5	5
4	6	20	7, 11, 13, 17, 19

Код программы (C++).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    cout<<"Primes: ";
    bool prime;
    int a,b;
    cin>>a>>b;
    vector<int> primes;
    for(int e=2; e<=b; e++)
    {
        prime=true;
        for(int i=0; i<primes.size(); i++)
        {
            if((e%primes[i])==0) prime=false;
        }
        if(prime==true)
        {
            primes.push_back(e);
            if(e>=a) cout<<e<<" ";
        }
    }
    if(b<2) cout<<"Not found.";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

cout<<"Primes: ";

bool prime;

int a,b;

cin>>a>>b;

vector<int> primes;

for(int e=2; e<=b; e++)

{

prime=true;

for(int i=0; i<primes.size(); i++)

{

if((e%primes[i])==0) prime=false;

}

if(prime==true)

{

primes.push_back(e);

if(e>=a) cout<<e<<" ";

}

if(b<2) cout<<"Not found.";

return 0;

}

Код программы (Java).

import java.util.*;
import java.math.*;
 
class sieveOfEratosthenes
{
    public void find(int a, int b){
        boolean[] prime = new boolean[b+1];
        Arrays.fill(prime, Boolean.TRUE);
        prime[0] = false;
        prime[1] = false;
        for(int i = 2; i <= b; ++i){
            if(prime[i]){
                for(int j = i*i; j <= b; j += i){
                    prime[j] = false;
                }   
            }   
        }
 
        boolean primes_found = false; //Попадает ли в промежуток хоть одно простое число?
        for(int i = a; i <= b; ++i){
            if(prime[i]){
                System.out.print(i + " ");
                primes_found = true;
            }
        }
        if(!primes_found) System.out.print("Not found");
    }
}
 
class Main
{
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        int a, b;
        a = in.nextInt();
        b = in.nextInt();
        sieveOfEratosthenes c = new sieveOfEratosthenes();
        c.find(a, b);
    }
}

import java.util.*;

import java.math.*;

class sieveOfEratosthenes

{

public void find(int a, int b){

boolean[] prime = new boolean[b+1];

Arrays.fill(prime, Boolean.TRUE);

prime[0] = false;

prime[1] = false;

for(int i = 2; i <= b; ++i){

if(prime[i]){

for(int j = i*i; j <= b; j += i){

prime[j] = false;

}

boolean primes_found = false; //Попадает ли в промежуток хоть одно простое число?

for(int i = a; i <= b; ++i){

if(prime[i]){

System.out.print(i + " ");

primes_found = true;

}

if(!primes_found) System.out.print("Not found");

}

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int a, b;

a = in.nextInt();

b = in.nextInt();

sieveOfEratosthenes c = new sieveOfEratosthenes();

c.find(a, b);

}

Решение.
C++:
Для начала, вводятся два целых числа. Очевидно, что придётся проверять, являются ли простыми числа, большие чем [latex]a[/latex] и меньшие чем [latex]b[/latex]. Не представляется возможным заранее узнать, насколько большими будут эти числа, потому, на мой взгляд, наиболее подходящим решением будет каждый запуск программы заново находить все простые числа до [latex]b[/latex]. Создаётся вектор, в котором они будут храниться (целесообразно использовать именно вектор, поскольку неизвестно точно, сколько чисел придётся хранить). Далее идёт цикл, в котором каждое число от двух до [latex]b[/latex], если оно не делится нацело ни на один из элементов вектора (это проверяется при по мощи вложенного цикла), добавляется в этот вектор и, если оно больше чем [latex]a[/latex], выводится. В случае, если [latex]b<2[/latex], очевидно, простые числа найдены не будут, потому выводится "Not found."
Java:
Решение на Java представляет собой реализацию Решета Эратосфена.
Код на ideone.com: C++, Java.
Условие задачи (с.135)

Related Images:

Совершенные числа

17/08/2016 by Макогон Владимир Сакович

Задача. Найдите все чётные совершенные числа не превышающие заданного числа[latex]M[/latex].

Напомним, что натуральное число [latex]n[/latex] называют совершенным, если оно равно сумме всех своих делителей, не считая его самого. Известно, что все совершенные числа — четные и что первое совершенное число из натурального ряда равно 6. Этим объясняется правило изменения параметра внешнего цикла. Так как все натуральные числа имеют своим делителем единицу, полагаем начальное значение суммы делителей числа S = 1. Во внутреннем цикле организуется перебор всех делителей текущего значения N. Из теории чисел известно, что такому испытанию имеет смысл подвергать числа от 2 до [latex]\frac{n}{2}[/latex], либо даже до [latex]\sqrt{n}[/latex]. Этот не очень совершенный алгоритм реализован в следующем коде:

#include <iostream>
#include <cmath>
using namespace std;

int main() {    
    unsigned long long M;
    cin >> M;
    for (unsigned long long n = 4; n <= M; n += 2) {
        unsigned long long S = 1;
        for (unsigned long long j = 2; j <= sqrt(n) && S <= n; j++) {
            if (n % j == 0) S += n / j + j;
        }
        if (n == S) cout << n << " ";
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

unsigned long long M;

cin >> M;

for (unsigned long long n = 4; n <= M; n += 2) {

unsigned long long S = 1;

for (unsigned long long j = 2; j <= sqrt(n) && S <= n; j++) {

if (n % j == 0) S += n / j + j;

}

if (n == S) cout << n << " ";

}

return 0;

}

Обратите внимание, что во внутреннем цикле мы прекращаем искать делители, если их сумма уже превышает исходное число.

Теперь рассмотрим другой подход, позволяющий ускорить вычисления. Используем алгоритм нахождения совершенных чисел, более эффективный по сравнению с приведенным ранее. Этот алгоритм основан на известном из теории чисел утверждении Ферма о том, что если натуральное число [latex]p = 2^{k+1}-1[/latex] простое, то число [latex]n = 2^k \cdot (2^{k+1}-1)=p \cdot 2^k[/latex] — совершенное ([latex]k = 1,2,\ldots[/latex]).
Функция prime() определяет, является ли число [latex]p[/latex] простым. Обратите внимание, что функция проверяет в качестве возможных делителей исходного числа только нечетные числа, так как само испытуемое число — нечетное.

// Найти все чётные совершенные числа из unsigned long long
#include <iostream>
#include <cmath>
using namespace std;

// Подпрограмма определяет, является ли число n простым
bool is_prime(unsigned long long n) {  
    unsigned long long  i = 3;
    while (i < sqrt(n)) {
        if (n % i == 0) return false;
        i += 2;
    }
    return true;
}

int main() {
    unsigned long long p = 1, n = 1;
    while (p * n < (4 * n - 1) * 2 * n) { // пока числа увеличиваются
        p = 2 * n - 1; 
        if (is_prime(p)) cout << n * p << " ";
        n <<= 1;
    } 
    return 0;
}

// Найти все чётные совершенные числа из unsigned long long

#include <iostream>

#include <cmath>

using namespace std;

// Подпрограмма определяет, является ли число n простым

bool is_prime(unsigned long long n) {

unsigned long long i = 3;

while (i < sqrt(n)) {

if (n % i == 0) return false;

i += 2;

}

return true;

}

int main() {

unsigned long long p = 1, n = 1;

while (p * n < (4 * n - 1) * 2 * n) { // пока числа увеличиваются

p = 2 * n - 1;

if (is_prime(p)) cout << n * p << " ";

n <<= 1;

}

return 0;

}

Отметим, что это очень эффективный алгоритм: приведенные результаты были получены программой практически мгновенно. Программа из предыдущей задачи за разумное время этого сделать не может.
Вывод: если алгоритм плохой, то программа хорошей быть не может.
К сожалению, алгоритм не гарантирует нахождения всех совершенных чисел.

Задача

Входные данные

Выходные данные

Тесты

Код

Решение

Ссылки

Related Images:

Task

Input

Output

Tests

Code

Solution

Links

Related Images:

Задача

Входные данные

Выходные данные

Тесты

Код программы с использованием цикла

Код программы с использованием условных операторов

Решение

Условные операторы

Цикл

Ссылки

Related Images:

Задача

Входные данные

Выходные данные

Тесты

Код решения

Решение

Related Images:

Сумма всех

Входные данные

Выходные данные

Тесты

Код программы

Решение задачи

Ссылки

Related Images:

Related Images:

Related Images:

Задача

Входные данные:

Выходные данные:

Тесты

Код программы

Решение

Ссылки

Related Images:

Related Images:

Related Images: