Удаление незначащих нулей из решета Эратосфена - 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); } } /****************/
Объяснение кода листинга программы
- Включаем необходимые заголовочные файлы для работы с массивами, математикой и файловой системой
- Объявляем статические переменные: массив Rest размером 8, указатель A на массив размером V и переменную V для хранения размера массива A
- Определяем константу N, до которой будет строиться решето
- В функции main() объявляем переменные ii, p, jj, s
- Вычисляем размер массива V как N/30 + 1 и выделяем память под массив A с помощью функции malloc()
- Инициализируем первый элемент массива A значением 1, а все остальные нулями с помощью функции memset()
- Вычисляем значение переменной s как квадратный корень из N
- В цикле от 0 до s перебираем все числа от 0 до N, для которых A[ii] == 1, устанавливаем соответствующие биты в массиве A в 1
- В функции Jolting(int p) объявляем переменные x, d, r, i
- В цикле x = 7p; x += 2p; x += 2p перебираем все числа от 7p до 2*N
- Вычисляем значение переменной d как x/30
- Если d >= V, выходим из цикла
- Вычисляем значение переменной r как x%30
- Перебираем все числа от 0 до 8, если r == Rest[i], выходим из цикла
- Устанавливаем соответствующий бит в массиве A в 1
- В основной функции main() перебираем все числа от 0 до V и выводим на экран значения, для которых A[ii] == 1, с помощью функции printf()
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д