Сито Эратосфена и гипотеза Гольдбаха
Внедрите Сито Эратосфена и используйте его, чтобы найти все простые
числа меньше или равны одному миллиону. Используйте результат для
доказать гипотезу Гольдбаха для всех четных целых чисел от четырех до
один миллион включительно.
Реализуйте функцию со следующим объявлением:
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 ++;
}
}
моя проблема в том, что он отображает числа выше 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
}
}
Других решений пока нет …