Тема: Знаходження простих чисел перебором дільників і решето Ератосфена
Допоможіть, будь ласка, виконати ці завдання (проблему описав в кінці):
1) Реалізувати алгоритм знаходження простих чисел звичайним перебором
дільників, для цього створити функцію яка перевіряє одне число на
простоту: bool isPrime(int number) { ... }
Виконати задачу по варіанту, заміряти час роботи.
2) Реалізувати алгоритм «Решето Ератосфена» для знаходження всіх
простих чисел на проміжку від 1 до N. Виконати задачу по варіанту,
заміряти час роботи.
3) Перевірити правильність результатів роботи обох алгоритмів на різних
вхідних даних, порівняти їх швидкодію.
Завдання за моїм варіантом:
Знайти добуток найбільшого та найменшого трицифрових простих чисел.
Ось мій код:
#include <iostream>
#include <windows.h>
#include <locale.h>
using namespace std;
bool isPrime(int n)
{
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i == 0)
{
return false;
}
}
return true;
}
int isPrimeE(int n)
{
const int N = 1001;
bool primeNumbers[N] = { true };
primeNumbers[0] = primeNumbers[1] = false;
for (int i = 2; i * i <= n; i++)
{
if (primeNumbers[i])
{
for (int j = i * i; j <= n; j += i)
{
primeNumbers[j] = false;
}
}
}
}
int main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
int n;
cout << "Введіть число: ";
cin >> n;
cout << isPrime(n) << endl;
cout << isPrimeE(n) << endl;
system("pause");
return 0;
}Проблема в тому, що функція "isPrimeE" (решето Ератосфена) працює не правильно і я не знаю в чому проблема і як це виправити (скоріше всього функція повинна щось повертати, а я не можу зрозуміти що саме, а може проблема і не в цьому, я вже заплутався). І ще я не можу зрозуміти як реалізувати завдання за моїм варіантом, особливо в першій функції, ідей взагалі немає.
Тому дуже прошу Вас про допомогу, буду щиро вдячний!
