Задача "Суперчисла"

Question

Имеется задача:

Суперчислом называется число, являющееся суммой двух простых чисел из диапазона [2…B]. Требуется найти все суперчисла из заданного диапазона [A…B]. (2 <= A <= B <= 40000)
Пример: Ввод: 3 10; Вывод: 4 5 6 7 8 9 10

Я написал код Python:

a, b = map(int, input().split())
 
prime = [x for x in range(b + 1)]
prime[1] = 0
prime_list = []
 
i = 2
while i <= b:
    if prime[i] != 0:
        prime_list.append(prime[i])
        for j in range(i, b - 1, i):
            prime[j] = 0
    i += 1
 
ans = []
for i in range(len(prime_list)):
    for x in range(0, len(prime_list) - 1):
        g = prime_list[i] + prime_list[x]
        ans.append(g) if g <= b and g >= a else None
 
ans = sorted(list(set(ans)))
for x in ans:
    print(x)

И на С++

#include <iostream>
#include <vector>
#include <set>
using namespace std;
int main()
{
    int a; int b;
    cin >> a >> b;
    vector<int> prime (0);
    vector<int> prime_list (0);
    for (int i = 0; i <= b; i++)
        prime.push_back(i);
    prime[0] = 1;
    int i = 2;
    while (i <= b)
    {
        if (prime[i] != 0)
        {
            prime_list.push_back(prime[i]);
            for (int j = i; j < b - 1; j *= 2)
                prime[j] = 0;
        }
        i += 1;
    }
    set<int> ans;
    for (int i = 0; i < prime_list.size(); i++)
    {
        for (int x = 0; x < prime_list.size() - 1; x++)
        {
            int g = prime_list[i] + prime_list[x];
            if (g <= b && g >= a)
                ans.insert(g);
        }
    }
    for (int x: ans)
        cout << x << endl;
}

Python благополучно прошёл все тесты, но С++ "Выдаёт ошибку в процессе выполнения".
Подскажите пожалуйста, что не так с С++ кодом? (Тестовые данные мне не известны)

Answer 1

Не хотите немного короче?

#include <vector>
#include <iostream>
#include <set>
#include <iomanip>

using namespace std;

bool p[40000] = { false };

int main(int argc, char * argv[])
{
    vector<int>ps;
    int a, b;
    cin >> a >> b;
    for(int i = 2; i < b; ++i)
        if (p[i] == false)
        {
            ps.push_back(i);
            for(int j = i*2; j < b; j += i) p[j] = true;
        }
    set<int>s;
    for(int i = 0; i < ps.size(); ++i)
        for(int j = i; j < ps.size(); ++j)
        {
            int x = ps[i]+ps[j];
            if (x < a ) continue; 
            if (x <= b) s.insert(x); else break;
        }
    for(int x: s) cout << x << " ";
}

Answer 2

Добавляем отладочную печать:

    if (prime[i] != 0)
    {
        cout << "prime " << i << '\n'; // debug print
        prime_list.push_back(prime[i]);
        for (int j = i; j < b - 1; j *= 2)
            prime[j] = 0;
    }

$ echo 10 20 | ./a.out 
prime 2
prime 3
prime 5
prime 7
prime 9       # ???
prime 11
prime 13
prime 15      # ???
prime 17
prime 19
prime 20      # ???

Непорядок в заголовке цикла for. Исправляем (это минимальная правка, есть варианты быстрее):

    if (prime[i] != 0)
    {
        cout << "prime " << i << '\n'; // debug print
        prime_list.push_back(prime[i]);
        for (int j = i; j <= b; j += i)
            prime[j] = 0;
    }

$ echo 10 20 | ./a.out 
prime 2
prime 3
prime 5
prime 7
prime 11
prime 13
prime 17
prime 19

Стало лучше. Ошибка верхней границы перекочевала из Питона, ошибка с шагом цикла - новодел.

БЛОГ НА HUSL

Задача "Суперчисла"

Ответы (2 шт):