1

Тема: Решето Ератосфена (проблема у перевірці умови)

Нібито все правильно, але не виконується перевірка умови коли j ділиться на i без залишку.
Щось потрібно змінити в умові і я не розумію що

#include "stdafx.h"
#include <iostream>
#include <locale>

using namespace std;

int  main()
{
setlocale(LC_ALL, "ukrainian"); 
    int i, j=2, S;
    int N;
    bool *mas;

    cout << "Прості числа від 1 до N \n";
    cout << "Введіть число N ";
    cin >> S;
    N = S + 1;
    mas = new bool[N]; //динамично виділяємо пам’ять під масив розміром N

    for (i = 1; i <= S; i++) mas[i] = true; //заповнення масиву true;

    for (i = 2; i <= S; i++){
        for (j = 2; j <= S; j++){
            if (j % i > 0)
            {
                mas[j] = false;
            }
        }
    }    
    // Виведення значень масива
    for (i = 1; i <= S; i++)
    if (mas[i]) cout << i << " ";
system("pause");
return 0;
}

Дякую

2

Re: Решето Ератосфена (проблема у перевірці умови)

Може краще так?: http://purecodecpp.com/archives/2517

3

Re: Решето Ератосфена (проблема у перевірці умови)

Визначення простого числа ви правильно розумієте? Це число, яке не ділиться ні на що, окрім себе та 1. Уважно подивіться - ви ж перевіряєте, чи ділиться воно на себе!
Крім того, решето не так працює. Беремо перший true в списку і всім, хто на нього ділиться (тільки не ділимо, а додаємо!) ставимо false. Тобто є mas[2]==true - значить, для всіх 2+2+2+...+2 (цикл від 2 до N з переходом j+=2) ставимо false. Беремо наступний true (3) і т.д.