Fluxŭs

// primi3.c
// ricerca dei numeri primi fino a 4 miliardi
// con il metodo del crivello di Eratostene
// scritto a scopo didattico da Vinicio Coletti
// febbraio 2022
// modificato qualche giorno dopo, per avanzamento dinamico

#include <stdio.h>
#include <string.h>

char flag[250000000];
unsigned n, np, byte, doppio, avan;
long i;
char bit;
FILE *f;

int main() {
   f=fopen("primi.bin","w");
   np=1;
   n=2;
   // scrive il numero 2
   fwrite(&n,4,1,f); 
   // azzera vettore dei flag
   memset(flag,0,sizeof(flag)); 
   // inizializza maschera avanzamento dinamico
   avan=1;
   // ciclo sui num. dispari, dal 3
   for (n=3;n<4000000000U;n+=2) { 
      // mostra avanzamento in modo dinamico
      if ((n&avan)==1) {
         printf("%u\n",n);
         avan=(avan<<1)|1;
      }
      // trova posizione del flag, byte e maschera bit
      byte=n>>4;
      bit=1<<(char)((n&15)>>1);
      // controlla se il flag è zero -> numero primo
      if (!(flag[byte]&bit)) {
         // qui trovato primo, incrementa conteggio
         np++;
         // scrive il numero nel file
         fwrite(&n,4,1,f);
         // imposta il flag nei multipli, partendo dal triplo
         // perche' ci sono solo numeri dispari
         doppio=n<<1;
         for (i=n*3L;i<4000000000L;i+=doppio) {
            byte=i>>4;
            bit=1<<(char)((i&15)>>1);
            flag[byte]|=bit;
         }
      }
   }
   fclose(f);
   // mostra numero di primi trovati
   printf("Primi = %u\n",np);
}

// mostra i numeri primi compresi tra due limiti
// a partire da un file binario con numeri interi
// uso: vediprimi nomefile min max
// scritto a scopo didattico
// da Vinicio Coletti - febbraio 2022
// modificato giorni dopo, per ricerca binaria dell'inizio

#include <stdio.h>
#include <stdlib.h>

FILE *f;
unsigned num, min, max;
int tot;
long pos, bot, top;

int main(int argc, char **argv) {
   if (argc>3) {
      min=(unsigned)atoi(argv[2]);
      max=(unsigned)atoi(argv[3]);
      f=fopen(argv[1],"r");
      fseek(f,-4,SEEK_END);
      top=ftell(f)>>2;
      bot=0;
      // ricerca binaria di un numero appena >= min
      while (top-bot>1) {
         pos=((top+bot)>>1)<<2;
         fseek(f,pos,SEEK_SET);
         tot=fread(&num,4,1,f);
         if (num==min) break;
         if (num>min) top=pos>>2;
         else bot=pos>>2;
      };
      if (num!=min) pos=bot<<2;
      fseek(f,pos,SEEK_SET);
      tot=0;
      while (1==fread(&num,4,1,f)) {
         if (num>=min && num<=max) {
            printf("%11u",num);
            tot++;
            if (!(tot%6)) printf("\n");            
         }
         if (num>max) break;
      } 
      fclose(f);
      if (tot%6) printf("\n");
   }
}

// programma per ricerca dei numeri primi
// fino a 1 milione, con il metodo delle divisioni
// algoritmo non ottimizzato, a scopo didattico
// scritto da Vinicio Coletti - febbraio 2022

#include <stdio.h>

int p[250000];
int n, np, i;
FILE *f;

int main() {
   np=0;
   f=fopen("primi.txt","w");
   for (n=2;n<1000000;n++) {
      for (i=0;i<np;i++) {
         if (!(n%p[i])) break;
      }
      if (i==np) {
         p[np++]=n;
         fprintf(f,"%7d",n);
         if (!(np&7)) fprintf(f,"\n");
      }
   }
   if (np&7) fprintf(f,"\n");
   fclose(f);
   printf("Primi = %d\n",np);
}

// programma per ricerca dei numeri primi
// fino a 1 milione, con il metodo delle divisioni
// algoritmo ottimizzato, a scopo didattico
// scritto da Vinicio Coletti - febbraio 2022

#include <stdio.h>
#include <math.h>

int p[250];
int n, np, i, max;
FILE *f;

int main() {
   np=1;
   f=fopen("primi2.txt","w");
   fprintf(f,"%7d",2);
   for (n=3;n<1000000;n+=2) {
      max=(int)floor(sqrt((double)n));
      for (i=1;p[i]<=max && i<np;i++) {
         if (!(n%p[i])) break;
      }
      if (p[i]>max || i==np) {
         if (np<250) p[np]=n;
         np++;
         fprintf(f,"%7d",n);
         if (!(np&7)) fprintf(f,"\n");
      }
   }
   if (np&7) fprintf(f,"\n");
   fclose(f);
   printf("Primi = %d\n",np);
}

// 8 regine su una scacchiera
// esteso a NUM regine su scacchiera NUM x NUM
// quarto metodo
// scritto da Vinicio Coletti, febbraio 2022

#include <stdio.h>
#include <sys/time.h>
#include <string.h>
#include <stdlib.h>

short NUM=8;
short menouno;
short reg[1000];
int tot, i;
__uint64_t inizio, fine;
FILE *f;
char riga[1000], ds[1999], dd[1999];

__uint64_t tempo() {
   struct timeval tv;
   gettimeofday(&tv,NULL);
   return tv.tv_sec*(__uint64_t)1000000+tv.tv_usec;
}

void muovi(short col) {
   short r, c;
   for (r=0;r<NUM;r++) {
      if (riga[r]||ds[col+r]||dd[col-r+menouno]) continue;
      reg[col]=r;
      if (col<menouno) {
         riga[r]=1;
         ds[col+r]=1;
         dd[col-r+menouno]=1;
         muovi(col+1);
         riga[r]=0;
         ds[col+r]=0;
         dd[col-r+menouno]=0;
      }
      else {
         fwrite(reg,NUM*2,1,f);
         tot++;
         // for (c=0;c<NUM;c++) printf("%4d ",reg[c]+1);
         // printf("\n");       
      }
   }
}

int main(int argc, char **argv) {
   if (argc>1) NUM=atoi(argv[1]);
   if (NUM<1||NUM>1000) { 
      printf("Numero errato regine: %d\n",NUM);
      exit(1);
   }
   menouno=NUM-1;
   tot=0;
   memset(riga,0,sizeof(riga));
   memset(ds,0,sizeof(ds));
   memset(dd,0,sizeof(dd));
   f=fopen("regine.out","w");
   inizio=tempo();   
   muovi(0);
   fine=tempo();
   fclose(f);
   printf("Regine = %d\n",NUM);
   printf("Soluzioni = %d\n",tot);
   printf("Microsecondi = %ld\n",fine-inizio);
}