1

Только смог осилить решето...

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

using namespace std;
int main()
{
const int N = 200;
bool a[N] = { 0 };
unsigned int n, i, j;
for (i = 2; i < N; i++)  a[i] = 1;

n = sqrt(double(N));

for (i = 2; i <= n; i++)
    if (a[i])
        for (j = i * 2; j < N; j += i)
            a[j] = 0;

for (i = 0; i < N; i++)
    if (a[i])
        cout << i << "  ";       

cout << endl;

system("pause");
return 0;
}
5
  • 1
    И в чём конкретно проблема?
    – Alexey Ten
    16 ноя 2018 в 20:33
  • Как разложить число используя решето Эратосфена?
    – user314318
    16 ноя 2018 в 20:35
  • Это у вас в заголовке написано. Для разложения на простые множители нужно искать простые делители.
    – Alexey Ten
    16 ноя 2018 в 20:38
  • Как мне это сделать?
    – user314318
    16 ноя 2018 в 20:41
  • Ну у вас уже есть простые числа (наверное), в чём проблема найти среди них делители?
    – Alexey Ten
    16 ноя 2018 в 20:42

2 ответа 2

1

Во первых думаю писать так будет чуть быстрей. Это будет видно при больших числах

for(int i = 1;i <= sqrt(n);++i)
    if(a[i])
        for(int j = i * i;j <= n;j += i)
            a[j] = 0

А ответ на ваш вопрос. Можно и не делать решето.

for(int i = 2;;++i){
    if(n % i){
        while(n % i == 0){
            n = n / i;
        }
        cout << i << endl;
    }
    if(n <= 1)break;
}

Выйдут все простые делители числа n. А если хотите делать с решето то на словах объясню.

Надо пройтись через все числа которые меньше N(проверяемое число) в решето.Если у него 1 значит это простое число и проверяем делит ли он N. Если да то выводите. Теперь у вас все делители числа N.

0

Брать простое число и делить на него исходное число, пока остаток от деления не перестанет быть равным нулю. Потом переходить к следующему простому числу.

3
  • Только сначала попробовать это же ещё раз.
    – Alexey Ten
    16 ноя 2018 в 20:41
  • @AlexeyTen Первое предложение подразумевает множество делений.
    – user176262
    16 ноя 2018 в 20:43
  • @AnT А откуда у него возьмутся простые числа? Из решета.
    – user176262
    16 ноя 2018 в 20:44