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

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

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

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

13.01.2013, 17:47. Просмотров 777. Ответов 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++
В решете эратосфена из книги в условии есть непонятная вещь: if (i * 1ll * i &lt;= n) - возле единицы для непонятных знака, на форуме они...

Решето Эратосфена - C++
Кому надо - программа &quot;Решето Эратосфена&quot; на C++. Записывает в файл 1 000 000 первых простых чисел за 1/10 секунды (без вывода)!!! ...

Решето Эратосфена - C++
Дано число N (2&lt;=N &lt;=10000), найдите и выведите простые числа между 2 и данным N. Простое число - число, которое может быть разделено...

Решето Эратосфена - C++
Здравствуйте. Реализовал алгоритм &quot;Решето Эратосфена&quot; в виде класса. Взгляните, пожалуйста, и скажите, где я не прав. Спасибо. ...

Решето Эратосфена - C++
Подскажите реализацию (код) метода шифрования - решета Эратосфена, пожалуйста.

Решето Эратосфена - C++
Написать функция для выполнения алгоритма решить Эратосфена! зарания спасибо!!!

Решето Эратосфена - C++
Определить простые числа методом просеивания с помощью &lt;&lt;решета Эратосфена&gt;&gt; с _битовой упаковкой_ данных при сохранении. #include...

Решето Эратосфена с графикой - C++
Нужно сделать решето эратосфена, с введением чисел от 2 до N, и чтобы выводил все числа и вычеркивал, не знаю как это реализовать, знания...

Простые числа. Решето Эратосфена - C++
Здравствуйте! Нужна ваша помощь, не могу понять условие этой задачи: Даны натуральное число n, целые числа a1,.....,an. Рассмотреть...

Решето Эратосфена. Как ускорить? - C++
Этот код не проходит задачу. доля секунды. как ускорить. или каким методом проидет #include &lt;bits/stdc++.h&gt; using namespace std; ...

Определить количество простых чисел, меньших N, используя решето Эратосфена - C++
Дан код: #include &lt;iostream&gt; using namespace std; static const int N = 1000; int main() { int i, a; for (i = 2; i &lt; N; i++)...

Объяснить работу программы (нахождение простых чисел, решето Эратосфена) - C++
Поясните как работает эта прога а именно : #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; int main() { ...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
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     Решето Эратосфена
Ответ Создать тему
Опции темы

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