Удаление незначащих нулей из решета Эратосфена - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Я создал решето Эратосфена (решето простых чисел), но не могу сделать так, что бы в решете остались только простые числа без нулей. Сейчас программа выводит : 0 2 3 0 5 0 7 0 0 0 11 0 13... (где 0 - это бывшие составные числа). Помогите пожалуйста сделать так, чтобы Решето было без 0. Использование решета обязательно. Заранее большое спасибо!
вот моя программа на си:
#include <stdio.h>
#include <math.h>
main() {
        int i,j,q,f;
    int n,max;
    scanf("%d", &n);
    q=(sqrt(n)*30);
    int a[q];

        /*Создание Решета с 0(для составных чисел) и 1(для простых) */
    a[1]=0;
    for (i=2;i<=q;i++)
        a[i]=1;
    for (i=2;i*i<=q;i++) {
        if(a[i]==1) {
            for (j=i*i;j<=q;j+=i)
                a[j]=0;
        }
    }

    for (i=1;i<=q;i++) {
        if (a[i]==1)
            a[i]=i;
        }
        for (i=1;i<=q;i++)
                printf("%d", a[i]);
}

Решение задачи: «Удаление незначащих нулей из решета Эратосфена»

textual
Листинг программы
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
static int Rest[8] = { 1, 7, 11, 13, 17, 19, 23, 29 };
static unsigned char *A;
static int V; // Объем массива A
#define N 12000  // До какого числа строить решето
main()
{ int s, p, ii, jj;
   V = N/30 + 1;
   A = (unsigned char *)malloc(V);
   A[0] = 1;
   memset(A+1, 0, V-1);
   s = sqrt(N);
   for(ii=p=0; p<=s; ii++) {
     for(jj=0; jj<8; jj++) {
       if (A[ii] &(1<<jj)) continue;
       p = 30*ii + Rest[jj]; // Простое
       Jolting(p);
     }
   }
   for(ii=0; ii<V; ii++) {
     for(jj=0; jj<8; jj++) {
       if (A[ii] & (1<<jj)) continue;
       printf ("%d\n", 30*ii + Rest[jj]);
     }
   }
 
}
/****************/
Jolting(int p)
{ int x, d, r, i;
 
   for(x=7*p; ; x += 2*p) {
     d = x/30;
     if (d >= V) break;
     r = x%30;
     for(i=0; i<8; i++) if (r==Rest[i]) break;
     if (i==8) continue;
     A[d] |= (1<<i);
   }
}
/****************/

Объяснение кода листинга программы

  1. Включаем необходимые заголовочные файлы для работы с массивами, математикой и файловой системой
  2. Объявляем статические переменные: массив Rest размером 8, указатель A на массив размером V и переменную V для хранения размера массива A
  3. Определяем константу N, до которой будет строиться решето
  4. В функции main() объявляем переменные ii, p, jj, s
  5. Вычисляем размер массива V как N/30 + 1 и выделяем память под массив A с помощью функции malloc()
  6. Инициализируем первый элемент массива A значением 1, а все остальные нулями с помощью функции memset()
  7. Вычисляем значение переменной s как квадратный корень из N
  8. В цикле от 0 до s перебираем все числа от 0 до N, для которых A[ii] == 1, устанавливаем соответствующие биты в массиве A в 1
  9. В функции Jolting(int p) объявляем переменные x, d, r, i
  10. В цикле x = 7p; x += 2p; x += 2p перебираем все числа от 7p до 2*N
  11. Вычисляем значение переменной d как x/30
  12. Если d >= V, выходим из цикла
  13. Вычисляем значение переменной r как x%30
  14. Перебираем все числа от 0 до 8, если r == Rest[i], выходим из цикла
  15. Устанавливаем соответствующий бит в массиве A в 1
  16. В основной функции main() перебираем все числа от 0 до V и выводим на экран значения, для которых A[ii] == 1, с помощью функции printf()

Оцени полезность:

5   голосов , оценка 3.2 из 5
Похожие ответы