0

Решил написать свою версию на С "решето Эратосфена" на сегменте [2,M], Но почему-то считает неправильно. Например, 2 не входит в мое окончательное множество, и иногда появляется число (M+1)`

#include <stdio.h>
#include <stdlib.h>
int search(int p);
int main()
{
    int M;
    printf("Enter number(M): ");
    scanf("%d", &M);
    int array[M]; //VLA
    if (M <= 1) exit(1);
    for (int i = 2; i <= M; i++)
    {
        array[i] = search(i);
        printf("array[%d] = %d\n", i, array[i]);
    }
    return 0;
}

int search(int p)
{   
    int k;
    k = 0;
    for (int i = 2; i <= p; i++)
    {
        if(!(p % i))
        {
        k++;
        }
        if (!k) {return p; k = 0;}
    }
}
5
  • Первые (менее 10) простые числа обычно просто вписывают в код. Остальные проверяют.
    – Adokenai
    23 ноя 2018 в 2:26
  • Я просто решил в общем случае, так сказать, написать программу. Я вообще всегда так пишу обычно. 23 ноя 2018 в 2:27
  • Вопрос не в тему. ВОт многие на сайте пишут, например, алгоритм сложности O(N). Где можно найти литературу по сложности алгоритма? Как я понимаю, это связано с матаном, ибо O, o - символы Ландау. 23 ноя 2018 в 2:30
  • O() "большое О" - это оценка сложности. ru.wikipedia.org/wiki/… Например: О(1) - скорость обработки не меняется, О(N) - линейная зависимость.
    – Adokenai
    23 ноя 2018 в 2:36
  • А вы пробовали в гугле набирать Решето Эратосфена С?
    – demonplus
    23 ноя 2018 в 6:53

1 ответ 1

4

Приведённый код нельзя назвать решетом Эратосфена. По задумке он просто проверяет, простое ли число, для каждого из чисел диапазона.

Решето же не требует делений и проверок. В массиве просто помечаются составные числа, а в конце из него выбираются непомеченные. Ideone

#include <stdio.h>

int main() {
int M = 12; 
int Primes[M + 1]; 
for (int i = 0; i <= M; i++) 
  Primes[i] = 1;
for (int i = 2; i * i <= M; i++) {
   if (Primes[i]) {
        int t = i * i;
        while (t <= M) {
            Primes[t] = 0;
            t += i;
        }
    } 
}    
for (int i = 2; i < M; i++) 
  if (Primes[i])
     printf("%d ", i);
return 0;   
}
2 3 5 7 11 
6
  • Да, Вы наверно правы, я вообще не то написал. 23 ноя 2018 в 3:05
  • Но у вас вроде Pascal, а как это на С делать без проверок? Там же нереально... 23 ноя 2018 в 5:56
  • 1
    Это псевдокод. Нет разницы, какой язык - главное - принцип. Вот рабочий код на С++
    – MBo
    23 ноя 2018 в 6:52
  • Я смотрел, но я хотел написать его в рамках С 23 ноя 2018 в 6:57
  • cout заменить на printf, и будет С
    – MBo
    23 ноя 2018 в 7:00

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.