Сито Эратосфена и гипотеза Гольдбаха

Question

Сито Эратосфена и гипотеза Гольдбаха

Внедрите Сито Эратосфена и используйте его, чтобы найти все простые числа, меньшие или равные одному миллиону. Используйте результат, чтобы доказать гипотезу Гольдбаха для всех четных целых чисел от четырех до одного миллиона включительно.

Реализуйте функцию со следующим объявлением:

void sieve (int array [], int num); Эта функция принимает целочисленный массив в качестве аргумента. Массив должен быть инициализирован значениями от 1 до 1000000. Функция модифицирует массив так, чтобы остались только простые числа; все остальные значения обнуляются. Эта функция должна быть написана для принятия целочисленного массива любого размера. Вы должны вывести для всех простых чисел от 1 до 1000000, но когда я проверяю вашу функцию, она может быть в массиве другого размера.

Реализуйте функцию со следующим объявлением:

void goldbach (int array [], int num); Эта функция принимает тот же аргумент, что и предыдущая функция, и отображает каждое четное целое число от 4 до 1000000 с двумя простыми числами, которые к ней добавляются. Цель здесь - обеспечить эффективную реализацию. Это означает отсутствие умножения, деления или модуля при определении, является ли число простым. Это также означает, что вторая функция должна эффективно найти два простых числа.

Вывод для вашей программы: все простые числа от 1 до 1000000 и все четные числа от 4 до 1000000 и два простых числа, которые суммируют его.

НЕ предоставляйте вывод или запись сеанса для этого проекта!

Это код, который у меня есть до сих пор, моя проблема в том, что он отображает числа больше 1000 как 1, как я могу это сделать, спасибо!

#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;

void sieve(int array[], int num);
void goldbach(int array[], int num);

const int arraySize = 1000000;
int nums[arraySize];

int main(){

    for (int i = 0; i <= arraySize; ++i)
        nums[i] = 1;

    nums[0] = nums[1] = 0;

    sieve(nums, arraySize);

    for(int i = 0; i < 10000; ++i){
        if (nums[i] > 0){
            cout << nums[i] << " "; 
        }
    }

    goldbach(nums, arraySize);

    return 0;
}


void sieve(int array[], int num) {

    int squareR = (int)sqrt(num);

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

        int k;
        if(array[i]){
            for(k = i*i; k <= num; k += i)
                array[k] = 0;
        }

        if (array[i] == 1){
            array[i] = i;   
        }     
    }
}


void goldbach(int array[], int num){

    int i, r = 0;
    for (i = 4; i <= num; i += 2){

        for (int j = 2; j <= i/2; j++)

            if (array[j] && array[i-j]) r ++;
    }
}

Answer 1

моя проблема в том, что он отображает числа выше 1000 как 1, как я могу это сделать

Это потому, что вы не обновляете значения в массиве выше 1000 здесь:

for(int i = 2; i <= squareR; ++i){
   ...
    if (array[i] == 1){
        array[i] = i;

ясно, что записи массива выше squareR не обновляются и остаются на том значении, которое вы их инициализировали, что 1,

Однако я не нуждаюсь в этом обновлении. Вы можете отбросить его и упростить свой код, сохраняя записи массива равными 1 (для простых чисел) или 0 (для простых чисел). с этим, и отобразить ваш результат, как это (в main):

for(int i = 0; i < arraySize; ++i){
    if (nums[i] != 0){
        // cout << nums[i] << " "; // <-- drop this
        cout << i << " ";          // <-- use this
    }
}