Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
washington12
0 / 0 / 0
Регистрация: 13.01.2013
Сообщений: 5
#1

Решето Эратосфена - C++

13.01.2013, 17:47. Просмотров 765. Ответов 4
Метки нет (Все метки)

В общем задание посчитать количество простых чисел до заданного числа N.
Написал такой алгоритм, работает только до 11 Уже час не могу понять почему....
Подскажите пожалуйста что не так.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
 
using namespace std;
 
int main()
{
    int n,i,j,k;
    bool a[20001];
    cin>>n;
    a[1]=false;
    k=n-1;
    for (i=2;i<=n;i++)
    a[i]=true;
    for (i=2;i*i<=n;i++)
        if (a[i]=true)
            for (j=i*i;j<=n;j=j+i)
                if (a[j]=true)
                {a[j]=false;
                k--;};
    cout<<k;
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.01.2013, 17:47     Решето Эратосфена
Посмотрите здесь:

Решето Эратосфена C++
Решето Эратосфена C++
C++ Решето Эратосфена
Решето Эратосфена C++
Решето Эратосфена C++
C++ Решето Эратосфена
C++ Решето Эратосфена
Решето Эратосфена C++
C++ Решето Эратосфена с графикой
C++ Решето Эратосфена
Простые числа. Решето Эратосфена C++
C++ Решето Эратосфена. Как ускорить?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
13.01.2013, 17:57     Решето Эратосфена #2
в чем смысл алгоритма? я чот не понял вы просто берете и n-2 элементам массива bool присваиваете true а потом смотрите что если у них у всех true тогда меняем на false и уменьшаем k в чем смысл, не проще было просто посмотреть на форуме как найти простое число и заполнить массив таким образом?
_script_
169 / 137 / 34
Регистрация: 01.05.2012
Сообщений: 414
13.01.2013, 18:08     Решето Эратосфена #3
Ошибка у вас глупая)
Оператор сравнения записан не правильно!
вместо
C++
1
if (a[j]=true)
надо
C++
1
if (a[j]==true)
ну а так алгоритм вроде правильный!
washington12
0 / 0 / 0
Регистрация: 13.01.2013
Сообщений: 5
13.01.2013, 18:11  [ТС]     Решето Эратосфена #4
спасибо большое) и вправду глупая) вы спасли часа 4 моей жизни)
Nixy
ComfyMobile
400 / 281 / 8
Регистрация: 24.07.2012
Сообщений: 916
13.01.2013, 18:25     Решето Эратосфена #5
я чот не очень понял как работает ваш алгоритм можете мне объяснить?

Добавлено через 5 минут
а хотя нашел псевдо код на википедии не надо спасибо
Yandex
Объявления
13.01.2013, 18:25     Решето Эратосфена
Ответ Создать тему
Опции темы

Текущее время: 23:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru