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

C для начинающих

Войти
Регистрация
Восстановить пароль
 
SadiQ228
4 / 4 / 1
Регистрация: 16.12.2016
Сообщений: 85
#1

Решето Эратосфена (работает некорректно) - C (СИ)

09.01.2017, 03:44. Просмотров 208. Ответов 12
Метки нет (Все метки)

вроде компилируется однако не работает корректно

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<stdio.h>
 
int main()
{
    int n,j,c;
    int i = 2;
 
    int mass [10] = {2};
    for (n = 0; n < 10; n++,i++)
        mass[n] = i;
 
    for(c=2; c<10; c++){
        if (mass[c] !=0){
            for(j = c*2; j<10; j+=c){
                mass[j]=0;
            }
        }
    }
 
 
 
 
 
          for(i=0; i<10; i++){
                   if(mass[i]!=0){
                        printf("%d\n", mass[i]);
          }
     }
}
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.01.2017, 03:44
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Решето Эратосфена (работает некорректно) (C (СИ)):

Решето Эратосфена - C (СИ)
Добрый день!помогите пожалуйста найти ошибку.код состоит из трех файлов.в первом из них-ошибка,подскажите,какая?остальные две части...

Не удается реализовать Решето Эратосфена - C (СИ)
задача: быстро найти простые числа. проблема в том, что в СИ разбираюсь плохо ( так что код может кому-то показаться наивным ). прошу найти...

Наибольший простой делитель числа и Решето Эратосфена - C (СИ)
Необходимо найти наибольший простой делитель числа &quot;n&quot;, используя решето Эратосфена. Программа работает для чисел &lt; 10^6. Но необходимо...

Нахождение первых пятиста простых чисел через решето Эратосфена - C (СИ)
На языке си

Получить все простые числа I, удовлетворяющие неравенству, используя решето Эратосфена - C (СИ)
Даны натуральные числа К, Ь (К &lt; Ь). Получить все простые числа I, удовлетворяющие неравенству: К &lt; I &lt; Ь, используя решето...

Битовое решето Эратосфена: Исправить второй цикл, чтобы уменьшилось время работы программы - C (СИ)
Доброго времени суток! Подскажите, пожалуйста, как исправить второй цикл, чтобы уменьшилось время работы программы (на данном этапе при...

12
ata
267 / 239 / 53
Регистрация: 28.10.2015
Сообщений: 709
09.01.2017, 05:21 #2
Первое, что бросилось в глаза: инициализация массива, а потом его заполнение, начиная с нулевого индекса (строки 8 и 9).
0
Байт
Эксперт C
16136 / 10414 / 1549
Регистрация: 24.12.2010
Сообщений: 19,715
09.01.2017, 10:26 #3
Цитата Сообщение от ata Посмотреть сообщение
Первое,
Да, это нелепо, но влиять ни на что не должно.
Цитата Сообщение от SadiQ228 Посмотреть сообщение
однако не работает корректно
Следует писать, что именно не так. Зачем же напрасно эксплуатировать наши экстрасенсорные способности?
Код отформатирован так, что логики программы не видно. И пустые строки его вовсе не украшают. Посмотрите на него в таком виде, может быть ошибка сама бросится в глаза
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
 
int main()
{
    int n, j, c;
    int i = 2;
    int mass [10];
    for (n = 0; n < 10; n++,i++)
        mass[n] = i;
    for(c=2; c<10; c++){
        if (mass[c] !=0){
            for(j = c*2; j<10; j+=c)
                mass[j]=0;
        }
    }
    for(i=0; i<10; i++) {
              if(mass[i]!=0)
                     printf("%d\n", mass[i]);
    }
}
0
Tenebris
2 / 2 / 0
Регистрация: 30.06.2015
Сообщений: 40
09.01.2017, 11:14 #4
Мне кажется проблема в том, что тут нет алгоритма решета Эратосфена.
0
Байт
Эксперт C
16136 / 10414 / 1549
Регистрация: 24.12.2010
Сообщений: 19,715
09.01.2017, 11:17 #5
Цитата Сообщение от Tenebris Посмотреть сообщение
тут нет алгоритма решета Эратосфена.
Что вы имеете в виду?
0
Tenebris
2 / 2 / 0
Регистрация: 30.06.2015
Сообщений: 40
09.01.2017, 11:24 #6
Байт, ну а в чем суть алгоритма? Решето должно проверять числа от 3 до n на то простые они или нет. Добавлять их в массив простых чисел и использовать этот массив, чтобы поверять число на простоту. Это как идея простейшей реализации. Я не увидел в коде автора чего-то похожего...
0
Байт
Эксперт C
16136 / 10414 / 1549
Регистрация: 24.12.2010
Сообщений: 19,715
09.01.2017, 11:35 #7
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Tenebris Посмотреть сообщение
Я не увидел в коде автора чего-то похожего...
Да все там есть! Не от 3-х, а от 2-х, но суть не в этом.
По идее код похож на правильный. И выдавать должен... А! Чушь он должен выдавать!
2 3 4 5 7 9
Запутался ТС между j и mass[j]
0
Tenebris
2 / 2 / 0
Регистрация: 30.06.2015
Сообщений: 40
09.01.2017, 11:57 #8
типо еще одна глупая реализация алгоритма нахождения простых чисел
и идея наверно другая должна быть у решета для того чтобы фильтровать их
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
 
int main()
{
    int counter = 0;
    bool check;
    int mass [100];
    for(int i=2;counter<100;i++)
    {
        check = true;
        for(int k=0;k<counter;k++)
        {
            if(i%mass[k]==0)
            {
                check = false;
                break;
            }
        }
        if(check)
        {
            mass[counter] = i;
            counter++;
        }
    }
          for(int i=0; i<100; i++)
          {
                 printf("%4d", mass[i]);
                if(i%10==9)
                printf("\n");
          }
}
Добавлено через 8 минут
может на форуме есть мессия, который сможет набросать более менее оптимальный код (т.к. в моем проверяются на простоту даже четные числа) *хитрая улыбка)
0
Байт
Эксперт C
16136 / 10414 / 1549
Регистрация: 24.12.2010
Сообщений: 19,715
09.01.2017, 12:25 #9
Tenebris, Это не решето. Старик Эратосфен здесь совершенно ни при чем
C
1
2
3
4
5
6
7
8
mas[100];
for(i=0; i<100;i++) mas[i] = 1;
for(k=2; k<=10; k++) {
  if (mas[k])
    for(j=k*2; j <100; j+=k) mas[j] = 0;
}
for(i=2; i<100; i++) 
  if (mas[i]) printf("%d\n", i);
Добавлено через 5 минут
Цитата Сообщение от Tenebris Посмотреть сообщение
может на форуме есть мессия
C
1
2
3
4
5
6
7
8
9
mas[100];
for(i=0; i<100;i++) mas[i] = i%2;
mas[2] = 1;
for(k=3; k<=10; k+=2) {
  if (mas[k])
    for(j=3*k; j <100; j+=2*k) mas[j] = 0;
}
for(i=2; i<100; i++) 
  if (mas[i]) printf("%d\n", i);
В первом коде была ошибочка. Исправил.

Добавлено через 10 минут
ЗЫ. Конечно, код еще не самый оптимальный. В самом деле удобнее хранить признаки простоты (собственно решето) в битах, по 8 бит на байт. При этом 1 байт может описывать 30 чисел (интересны только 8 чисел в каждой тридцатке с остатками 1, 7, 11, 13, 17, 19, 23, 29 ) не считая первой тридцатки. Экономия по памяти в 30*sizeof(int) = 120 раз. Но тут уже алгоритм будет чуток похитрее (на форуме встречалось)

Добавлено через 12 минут
Еще одна мелкая оптимизация. В строчке 6 (последний код)
C
1
for(j=k*k;...
2
SadiQ228
4 / 4 / 1
Регистрация: 16.12.2016
Сообщений: 85
09.01.2017, 22:26  [ТС] #10
Комрады выкладываю на общий стыд и призрение допиленной версии алгоритма Эратосфена для простых чисел.
Жду критику по делу, а так же указания на фундаментальные ошибки в мышлении при проектировании спасибо.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<stdio.h>
#define MAX 100
int main()
{
    int n, j, c;
    int i = 2;
    int mass [MAX];
    for (n = 0; n < MAX; n++)
        mass[n] = n;
        mass[1] = 0;
 
        for(c=2; c<MAX; c++){
                if (mass[c] !=0){
                    for(j = c*2; j<MAX; j+=c)
                        mass[j]=0;
                }
        }
 
    for(; i<MAX; i++) {
              if(mass[i]!=0)
                     printf("%d\n", mass[i]);
    }
}
0
Байт
Эксперт C
16136 / 10414 / 1549
Регистрация: 24.12.2010
Сообщений: 19,715
09.01.2017, 23:03 #11
SadiQ228, Работает? На первый взгляд - должно.
Цитата Сообщение от SadiQ228 Посмотреть сообщение
Жду критику по делу, а так же указания на фундаментальные ошибки в мышлении
Много лишних вычислений. Кое-какие соображения были приведены в предыдущих постах. Повторяться неохота.
Для примера. При c>2 уже совершенно не нужно проверять число c*2. Четные мы уже вычеркнули раньше.
Также, если мы рассматриваем число k, как "вычеркивающее", уже не нужно смотреть все до k2. Они уже вычеркнуты предыдущими.
Смотрите. k = 5. 10, 20 вычеркнуто двойкой, 15 - тройкой. Первое с подозрением на непростоту - 25, вот с него и надо начинать.
Напишите 100 чисел и попробуйте вдумчиво применить к ним решето. Карандашиком. Смотрите, какие числа вычеркиваете. Возможно, вас удивит, но начиная с 11 делать уже ничего не надо. 22, 33, 44, ...99 уже вычеркнуты предварительными проходами.

Добавлено через 12 минут
SadiQ228, Если вас всерьез интересует эта тема, вот интересный материал
Быстрая проверка натурального числа на простоту
1
SadiQ228
4 / 4 / 1
Регистрация: 16.12.2016
Сообщений: 85
09.01.2017, 23:12  [ТС] #12
Работает? На первый взгляд - должно.
а куда оно денется)))
Байт, она меня очень интересует как и сложность алгоритмов в целом, как явление
однако я лишь начал изучение, постигаю синтаксис и основные конструкции, и на данном этапе для меня важнее гораздо чтобы все работало без ошибок и сбоев выдавая искомые значения.
вам за помощь однозначно спасибо не вижу только как тут репутацию ставить

Добавлено через 5 минут
так например программа считает цифры для 1.000.000 и вылетает уже при 10.000.000

P.S. как в QT посмотреть время выполнения программы?
0
Байт
Эксперт C
16136 / 10414 / 1549
Регистрация: 24.12.2010
Сообщений: 19,715
09.01.2017, 23:24 #13
Цитата Сообщение от SadiQ228 Посмотреть сообщение
вам за помощь однозначно спасибо
Всегда пожалуйста
Цитата Сообщение от SadiQ228 Посмотреть сообщение
однако я лишь начал изучение, постигаю синтаксис и основные конструкции, и на данном этапе для меня важнее гораздо чтобы все работало без ошибок и сбоев выдавая искомые значения.
Ну что ж, подход правильный. Перед тем как разговаривать, надо знать язык.
Но не забудь и про математику. Теория чисел, Комбинаторика, Графы ... Ну и многое другое...

Добавлено через 7 минут
Цитата Сообщение от SadiQ228 Посмотреть сообщение
вылетает уже при 10.000.000
Переходи на long. Или что там есть. Памяти не хватает? - пиши в файл. Или используй более компактные представления. В конце концов все равно вылетит. Используй длинную арифметику. В общем, для больших чисел сложности вырастают. Эратосфену-то было легко. Придумал алгоритм - и гуляй. А в железе реализовать - тут думать надо. И смирись с тем, что натуральных чисел бесконечно много.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.01.2017, 23:24
Привет! Вот еще темы с ответами:

Некорректно работает if - C (СИ)
Здравствуйте. У меня проблема. Если я указываю такое условие: if ( (i != k) &amp;&amp; (j != l) ) то if срабатывает не всегда, но если...

Некорректно работает #define - C (СИ)
По идее, если что-нибудь ввести, то программа должна попытаться выполнить это как команду то есть если пользователь ввел printf (Hello...

Стек работает некорректно - C (СИ)
Почему он не прорабатывает до конца? #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; struct node { int value; node *next; ...

Функция работает некорректно - C (СИ)
Здравствуйте! Задача, написать функцию myfuc по заданному вызову ее int main(int argc, char *argv) { char *s = NULL; ...


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

Или воспользуйтесь поиском по форуму:
13
Yandex
Объявления
09.01.2017, 23:24
Ответ Создать тему
Опции темы

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