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

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

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

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

09.01.2017, 03:44. Просмотров 179. Ответов 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]);
          }
     }
}
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ata
264 / 236 / 53
Регистрация: 28.10.2015
Сообщений: 709
09.01.2017, 05:21     Решето Эратосфена (работает некорректно) #2
Первое, что бросилось в глаза: инициализация массива, а потом его заполнение, начиная с нулевого индекса (строки 8 и 9).
Байт
Эксперт C
15546 / 9888 / 1487
Регистрация: 24.12.2010
Сообщений: 18,494
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]);
    }
}
Tenebris
2 / 2 / 0
Регистрация: 30.06.2015
Сообщений: 40
09.01.2017, 11:14     Решето Эратосфена (работает некорректно) #4
Мне кажется проблема в том, что тут нет алгоритма решета Эратосфена.
Байт
Эксперт C
15546 / 9888 / 1487
Регистрация: 24.12.2010
Сообщений: 18,494
09.01.2017, 11:17     Решето Эратосфена (работает некорректно) #5
Цитата Сообщение от Tenebris Посмотреть сообщение
тут нет алгоритма решета Эратосфена.
Что вы имеете в виду?
Tenebris
2 / 2 / 0
Регистрация: 30.06.2015
Сообщений: 40
09.01.2017, 11:24     Решето Эратосфена (работает некорректно) #6
Байт, ну а в чем суть алгоритма? Решето должно проверять числа от 3 до n на то простые они или нет. Добавлять их в массив простых чисел и использовать этот массив, чтобы поверять число на простоту. Это как идея простейшей реализации. Я не увидел в коде автора чего-то похожего...
Байт
Эксперт C
15546 / 9888 / 1487
Регистрация: 24.12.2010
Сообщений: 18,494
09.01.2017, 11:35     Решето Эратосфена (работает некорректно) #7
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Tenebris Посмотреть сообщение
Я не увидел в коде автора чего-то похожего...
Да все там есть! Не от 3-х, а от 2-х, но суть не в этом.
По идее код похож на правильный. И выдавать должен... А! Чушь он должен выдавать!
2 3 4 5 7 9
Запутался ТС между j и mass[j]
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 минут
может на форуме есть мессия, который сможет набросать более менее оптимальный код (т.к. в моем проверяются на простоту даже четные числа) *хитрая улыбка)
Байт
Эксперт C
15546 / 9888 / 1487
Регистрация: 24.12.2010
Сообщений: 18,494
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;...
SadiQ228
4 / 4 / 1
Регистрация: 16.12.2016
Сообщений: 75
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]);
    }
}
Байт
Эксперт C
15546 / 9888 / 1487
Регистрация: 24.12.2010
Сообщений: 18,494
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, Если вас всерьез интересует эта тема, вот интересный материал
Быстрая проверка натурального числа на простоту
SadiQ228
4 / 4 / 1
Регистрация: 16.12.2016
Сообщений: 75
09.01.2017, 23:12  [ТС]     Решето Эратосфена (работает некорректно) #12
Работает? На первый взгляд - должно.
а куда оно денется)))
Байт, она меня очень интересует как и сложность алгоритмов в целом, как явление
однако я лишь начал изучение, постигаю синтаксис и основные конструкции, и на данном этапе для меня важнее гораздо чтобы все работало без ошибок и сбоев выдавая искомые значения.
вам за помощь однозначно спасибо не вижу только как тут репутацию ставить

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

P.S. как в QT посмотреть время выполнения программы?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.01.2017, 23:24     Решето Эратосфена (работает некорректно)
Еще ссылки по теме:

C (СИ) Некорректно работает прогрмма
Нахождение первых пятиста простых чисел через решето Эратосфена C (СИ)
C (СИ) Некорректно работает if
Битовое решето Эратосфена: Исправить второй цикл, чтобы уменьшилось время работы программы C (СИ)
C (СИ) Получить все простые числа I, удовлетворяющие неравенству, используя решето Эратосфена

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

Или воспользуйтесь поиском по форуму:
Байт
Эксперт C
15546 / 9888 / 1487
Регистрация: 24.12.2010
Сообщений: 18,494
09.01.2017, 23:24     Решето Эратосфена (работает некорректно) #13
Цитата Сообщение от SadiQ228 Посмотреть сообщение
вам за помощь однозначно спасибо
Всегда пожалуйста
Цитата Сообщение от SadiQ228 Посмотреть сообщение
однако я лишь начал изучение, постигаю синтаксис и основные конструкции, и на данном этапе для меня важнее гораздо чтобы все работало без ошибок и сбоев выдавая искомые значения.
Ну что ж, подход правильный. Перед тем как разговаривать, надо знать язык.
Но не забудь и про математику. Теория чисел, Комбинаторика, Графы ... Ну и многое другое...

Добавлено через 7 минут
Цитата Сообщение от SadiQ228 Посмотреть сообщение
вылетает уже при 10.000.000
Переходи на long. Или что там есть. Памяти не хватает? - пиши в файл. Или используй более компактные представления. В конце концов все равно вылетит. Используй длинную арифметику. В общем, для больших чисел сложности вырастают. Эратосфену-то было легко. Придумал алгоритм - и гуляй. А в железе реализовать - тут думать надо. И смирись с тем, что натуральных чисел бесконечно много.
Yandex
Объявления
09.01.2017, 23:24     Решето Эратосфена (работает некорректно)
Ответ Создать тему
Опции темы

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