С++: Уменьшение памяти в 8 раз

[Zealint]

venco в сообщении #541682 писал(а):

Zealint в сообщении #541675 писал(а):

Слово signed добавил лишь из эстетического чувства, заставшего меня в момент написания кода.

На всякий случай: в случае с "signed char" это важно, "signed char" и "char" - разные типы.

Да, я вспомнил, что вот видимо поэтому signed везде и написал. А иначе некрасиво было бы, везде нет, а для char есть.

Day в сообщении #541770 писал(а):

Для числа N его признак простоты мы храним не по адресу N, а по адресу вычисленному так

A = N/30;
  R = N%30;
  if (R==1) A+=1;
  else if (R==7) A+=2
  else if (R==11) A+=3
  // ......

а попробуйте это без if написать. Или все 8 остатков нереально будет красиво учесть битовыми трюками?
А лучше даже сделать заранее массив D[30], где D[i]="числу, которое нужно прибавить к A, когда R=i". Будет

A+=D[R];

И коль скоро пишем не на asm, лучше сделать R=N-A*30; Сейчас не знаю, а лет 10 назад это реально ускоряло выполнение, особенно на олимпиадах помогало.

[Alexu007]

Начинаем с 30.
По адресу 30+1 == 0, 31*2, 31*3, 31*4 и далее ставим 1.
Следующее 30+7 == 0, 37*2, 37*3 и далее - 1
...
30+11
30+13
30+17
...
30+29.
30*2 +1
...
30*2+29. И так до N. Так что-ли?

[Day]

Zealint в сообщении #541828 писал(а):

а попробуйте это без if написать. Или все 8 остатков нереально будет красиво учесть битовыми трюками?

Учту непременно. Тут я просто идею набросал, не осложняя ее битовыми трюками.

[Day]

Вот как-то так

#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);
   }
}
/****************/

Несколько первых простых пропущено, их можно добавить вручную Или немного модифицировать алгоритм.
Функцию Jolting можно слегка оптимизировать, чего я делать не стал, тк. нас в первую очередь интересует объем памяти.
Так же не стал заморачиваться на проблемах больших чисел и длинной арифметики.
Удачи!